初阶数据结构（C语言实现）——4.2队列

2.队列

2.1队列的概念及结构

队列：只允许在一端举行插入数据利用，在另一端举行删除数据利用的特别线性表，队列具有先辈先出FIFO(First In First Out) 入队列：举行插入利用的一端称为队尾 出队列：举行删除利用的一端称为队头

2.2队列的实现

队列也可以数组和链表的结构实现，利用链表的结构实现更优一些，由于假如利用数组的结构，出队列在数组头上出数据，服从会比力低。

• 队列结构
  

1. // 链式结构：表示队列
2. typedef struct QListNode
3. {
4. struct QListNode* _pNext;
5. QDataType _data;
6. }QNode;
7. // 队列的结构
8. typedef struct Queue
9. {
10. QNode* _front;
11. QNode* _rear;
12. }Queue;

复制代码

• 队列接口
  

1. // 初始化队列
2. void QueueInit(Queue* q);
3. // 队尾入队列
4. void QueuePush(Queue* q, QDataType data);
5. // 队头出队列
6. void QueuePop(Queue* q);
7. // 获取队列头部元素
8. QDataType QueueFront(Queue* q);
9. // 获取队列队尾元素
10. QDataType QueueBack(Queue* q);
11. // 获取队列中有效元素个数
12. int QueueSize(Queue* q);
13. // 检测队列是否为空，如果为空返回非零结果，如果非空返回0
14. int QueueEmpty(Queue* q);
15. // 销毁队列
16. void QueueDestroy(Queue* q);

复制代码

• 在VS2022中新建一个工程
  

   Queue20250310.h（队列的范例界说、接口函数声明、引用的头文件）
Queue20250310.c（队列的接口函数的实现）
QueueTest20250310.c（主函数、测试各个接口功能）
  2.2.1 初始化队列

1. // 初始化队列
2. void QueueInit(Queue* pq)
3. {
4.         assert(pq);
6.         pq->head = pq->tail = NULL;// 初始化队列的头指针和尾指针为NUL
7.         pq->size = 0; // 初始化队列的大小为0
8. }

复制代码

2.2.2 烧毁队列

1. // 销毁队列
2. void QueueDestroy(Queue* pq)
3. {
4.         assert(pq);
5.         QNode* cur = pq->head;// 定义一个指针指向队列的头节点
6.         while (cur)//遍历队列
7.         {
8.                 QNode* next = cur->next;//找到当前节点的下一个结点
9.                 free(cur);
10.                 cur = next;//继续往后走
11.         }
12.         pq->head = pq->tail = NULL;// 将队列的头指针和尾指针置为NUL
13.         pq->size = 0;//将队列的大小置为0
14. }

复制代码

2.2.3 队尾入队列

1. // 队尾入队列
2. void QueuePush(Queue* pq, QDataType data)
3. {
4.         QNode* newnode = (QNode*)malloc(sizeof(QNode));
5.         if (newnode == NULL)
6.         {
7.                 perror("QueueDestroy::malloc fail!");
8.                 return;
9.         }
10.         newnode->data = data;// 将数据存入新节点
11.         newnode->next = NULL;// 将新节点的指针域置为NULL
13.         if (pq->head == NULL)// 如果队列为空，则新节点即为队列的头指针和尾指针
14.         {
15.                 assert(pq->tail == NULL);
16.                 pq->head = pq->tail = newnode;
17.         }
18.         else //如果队列不为空，则将新节点插入到队列的尾部
19.         {
20.                 //尾插
21.                 pq->tail->next = newnode;
22.                 pq->tail = newnode;
23.         }
24.         pq->size++;// 队列的大小加1
25. }

复制代码

2.2.4 队头出队列

1. // 队头出队列
2. void QueuePop(Queue* pq)
3. {
4.         assert(pq);
5.         assert(pq->head==NULL);
7.         QNode* next = pq->head->next;                                                                                                                                                                                                                                                         
8.         free(pq->head); // 释放原头节点的内存空间
9.         pq->head = next;
10.         if (pq->head == NULL)// 如果队列为空，则将尾指针也置为NULL
11.                 pq->tail = NULL;
13.         pq->size--;
14. }

复制代码

2.2.5获取队列头部元素

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

复制代码

2.2.6 获取队列队尾元素

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

复制代码

2.2.7获取队列中有用元素个数

1. // 获取队列中有效元素个数
2. int QueueSize(Queue* pq)
3. {
4.         assert(pq);
6.         return pq->size;
7. }

复制代码

2.2.8 检测队列是否为空，假如为空返回非零结果，假如非空返回0

1. // 检测队列是否为空，如果为空返回非零结果，如果非空返回0
2. int QueueEmpty(Queue* pq)
3. {
4.         assert(pq);
6.         return pq->size == 0;// 如果队列的头指针为NULL，则队列为空
7. }

复制代码

3.栈和队列口试题

3.1 括号匹配题目。

括号匹配题目
3.2用队列实现栈。

用队列实现栈
3.3 用栈实现队列。

用栈实现队列
3.4 操持循环队列。

操持循环队列