系列文章目录

数据结构 —— 顺序表
数据结构 —— 单链表
数据结构 —— 双向链表
数据结构 —— 栈
数据结构 —— 队列

---

---

前言

数据结构是计算机存储、组织数据的方式。数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。数据结构是一种十分优秀的解决实际问题的模板，是先进思想的结晶。博主将会用代码结合大量图解，对数据结构进行深度剖析，以便大家更好的学习数据结构的思想。

---

一、示例问题：排队叫号

1.排队叫号流程

例如当我们到银行办理业务时，我们首先需要取号，银行按照号码顺序叫号，被叫到号的人去办理业务。

2.逻辑示意图

先取号的，先被叫号

3.队列的引入

队列的引入：先进先出，后进后出的数据结构

二、队列的概念

1.定义

队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出 FIFO(First In First Out)

• 入队列：进行插入操作的一端称为队尾
• 出队列：进行删除操作的一端称为队头

2.结构

队列的结构类型：由于只需要考虑头删和尾插，所以单链表的结构更适合队列

//类型
typedef int QDataType;

// 链式结构：表示队列
typedef struct QueueNode {
    QDataType data;
    struct QueueNode *next;
} QueueNode;

// 队列的结构
typedef struct Queue {
    QueueNode *head;
    QueueNode *tail;
} Queue;
1
2
3
4
5
6
7
8
9
10
11
12
13
14

3.存储

存储：用动态开辟的单链表来存储

三、队列的接口函数

1.初始化队列

对队列的内容进行初始设置

// 初始化队列
void QueueInit(Queue *que) {
    assert(que);
    que->head = que->tail = NULL;
}
1
2
3
4
5

2.空队列

判断是否为空队列

// 检测队列是否为空，如果为空返回非零结果，如果非空返回0
bool QueueEmpty(Queue *que) {
    assert(que);
    return que->head == NULL && que->tail == NULL;
}
1
2
3
4
5

3.入队（尾插）

队列的插入操作

// 队尾入队
void QueuePush(Queue *que, QDataType data) {
    assert(que);
    QueueNode *newNode = (QueueNode *)malloc(sizeof(QueueNode));
    if (newNode == NULL) {
        perror("malloc fail:");
    } else {
        newNode->next = NULL;
        newNode->data = data;
    }
    if (que->head == NULL) {
        que->head = que->tail = newNode;
    } else {
        que->tail->next = newNode;
        que->tail = que->tail->next;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

4.出队（头删）

队列的删除操作

// 队头出队
void QueuePop(Queue *que) {
    assert(que);
    assert(!QueueEmpty(que));
    if (que->head->next == NULL) {
        free(que->head);
        que->head = que->tail = NULL;
    } else {
        QueueNode *next = que->head->next;
        free(que->head);
        que->head = next;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13

5.头部元素

获取队列头部元素

// 获取队列头部元素
QDataType QueueFront(Queue *que) {
    assert(que);
    assert(!QueueEmpty(que));
    return que->head->data;
}
1
2
3
4
5
6

6.尾部元素

获取队列尾部元素

// 获取队列队尾元素
QDataType QueueBack(Queue *que) {
    assert(que);
    assert(!QueueEmpty(que));
    return que->tail->data;
}
1
2
3
4
5
6

7.队列的元素个数

获取队列中有效元素个数

// 获取队列中有效元素个数
int QueueSize(Queue *que) {
    assert(que);
    QueueNode *curr = que->head;
    int size = 0;
    while (curr) {
        curr = curr->next;
        size++;
    }
    return size;
}
1
2
3
4
5
6
7
8
9
10
11

8.销毁队列

释放栈申请的空间

// 销毁队列
void QueueDestroy(Queue *que) {
    assert(que);
    QueueNode *curr = que->head;
    while (curr) {
        QueueNode *del = curr;
        curr = curr->next;
        free(del);
    }
    que->head = que->tail = NULL;
}
1
2
3
4
5
6
7
8
9
10
11

---

四、总结

队列是解决实际问题时极其常用的一种数据结构，是非常重要的解决问题的方式。队列的各种接口的复现，有利于更好的学习数据结构的思想，有利于开阔视野，学习前辈的智慧结晶。对我们后续解决实际问题也会有很大帮助。