数据结构——队列

1. 概念与结构

队列（Queue）是一种先进先出（FIFO, First In First Out）的数据结构，即最先被插入队列的数据会最先被删除。队列广泛应用于计算机科学中，特别是在任务调度、缓冲区管理、网络数据传输等领域。

入队列：进行插入操作的一端称为队尾

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

2. 队列的底层结构分析

使用数组以及队列来实现队列的对比

1. 数组实现队列的基本原理

使用数组来实现队列时，可以借用一个固定大小的数组，维护两个指针：front 和 rear。

• front：指向队列的头部，表示第一个元素。
• rear：指向队列的尾部，表示下一个插入元素的位置。

当队列为空时，front == rear，而当队列满时，rear 达到数组的末尾。

1. Array: [ 1, 2, 3, 4, 5]
2. Front: 0, Rear: 5 (Queue is full)

复制代码

2. 链表实现队列的基本原理

使用链表实现队列时，我们可以通过 头指针（front） 和 尾指针（rear） 来维护队列。

• front：指向队列的头部（即第一个元素）。
• rear：指向队列的尾部（即最后一个元素）。

链表的每个节点包含数据部分和指向下一个节点的指针。队列的 入队 操作将元素添加到链表的尾部，出队 操作从链表的头部移除元素。

1. Head → [Data|Next] → [Data|Next] → [Data|Next] → NULL
2. Front → ↑
3. Rear → 指向尾部

复制代码

3. 数组队列与链表队列的对比

4.对比数组队列和链表队列的时间复杂度

总结

数组实现队列：

• 适用于队列大小已知或变化不大的情况，尤其在内存空间有限的情况下，简单且高效。但如果队列频繁增长，或者存在大量空间浪费，则不适合。
• 常见操作的时间复杂度为 O(1)，但在扩容时会有 O(n) 的时间复杂度，因为需要重新分配和复制数组。

链表实现队列：

• 适用于队列大小动态变化的场景，链表不需要预先分配大小，不会发生空间浪费，插入和删除操作高效。但链表实现需要更多的内存用于存储指针，操作也相对复杂。
• 常见操作的时间复杂度都是 O(1)，不涉及扩容问题，因此性能在这些操作上更加稳定。

综上 使用链表来实现队列

3. 队列的实现

1. //定义结点的结构
2. typedef int QDataTpe;
3. typedef struct QueueNode
4. {
5. QDataTpe data;
6. struct QueueNode* next;
7. }QueueNode;
9. //定义队列的结构
10. typedef struct Queue {
11. QueueNode* phead;//队头
12. QueueNode* ptail;//队尾
13. int size;//记录有效数据个数
14. }Queue;

复制代码

3.1 入队列

1. 创建新节点

• 每当我们将一个新的元素加入队列时，需要首先创建一个新的节点。这个节点会存储数据并且需要指向链表中的下一个节点。

• 需要分配内存来存储新节点，并将其 data 字段设置为要入队的数据，next 字段设置为 NULL（因为它是当前链表的最后一个节点）。

2. 检查队列是否为空

• 在进行入队操作之前，我们需要检查队列是否为空。队列为空时，新节点将成为队列的唯一元素，它既是头部节点也是尾部节点。
• 如果队列不为空，新节点将被添加到队列的尾部。

3. 将新节点添加到队列尾部

• 如果队列为空，直接将新节点赋给队列的 pq->phead 和 pq->ptail（即头指针和尾指针都指向新节点）。
• 如果队列不为空：
  • 更新当前队列尾部节点的 next 指针，指向新节点。
  • 更新队列的 pq->ptail 指针，指向新的尾部节点（新加入的节点）。

4. 确保尾指针正确更新

• 入队后，新的节点成为队列的尾部，因此需要更新队列的 pq->ptail 指针，确保它指向新的尾部节点。

1. //入队---队尾
2. void QueuePush(Queue* pq, QDataTpe x)
3. {
4. assert(pq);
5. //newnode
6. QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));
7. if (newnode == NULL)
8. {
9. perror("malloc fail!");
10. exit(1);
11. }
12. newnode->data = x;
13. newnode->next = NULL;
15. //队列为空，newnode是队头也是队尾
16. if (pq->phead == NULL)
17. {
18. pq->phead = pq->ptail = newnode;
19. }
20. else {
21. //队列非空，直接插入到队尾
22. pq->ptail->next = newnode;
23. pq->ptail = pq->ptail->next;
24. }
25. pq->size++;
26. }

复制代码

3.2 出队列

1. //判断队列是否为空
2. bool QueueEmpty(Queue* pq)
3. {
4. assert(pq);
5. return pq->phead == 0;
6. }

复制代码

pq->phead == 0：这部分代码在检查 phead 是否为空。0 在 C 语言中等价于 NULL，即表示指针没有指向任何有效的内存地址。

• 如果 phead 为 NULL，意味着队列为空，函数将返回 true（队列为空）。
• 如果 phead 不为 NULL，说明队列中至少有一个元素，函数将返回 false（队列非空）。

步骤说明：

假设我们有一个队列 Queue，它是通过链表实现的，其中 phead 指向队列的头部，ptail 指向队列的尾部。每个节点包含数据和指向下一个节点的指针。

1. 检查队列是否为空：

在进行出队操作之前，我们需要检查队列是否为空。如果队列为空，则不能出队，因为没有元素可供删除。

2. 保存头部元素的数据：

我们需要保存 phead 指针指向的元素数据，因为在删除节点时，我们将失去对该数据的引用。如果要返回出队的元素数据，必须先保存它。

3. 更新 phead 指针：

将 phead指向队列的下一个节点，即 phead = phead->next。这样，队列头部的元素就被“删除”了。phead 指针现在指向新的队头元素。

4. 处理队列为空的情况：

如果 phead 变为 NULL，即队列中没有元素时，需要将 ptail 指针也设置为 NULL，因为队列为空时，phead 和 ptail 都应该为 NULL。

5. 释放已删除节点的内存：

如果我们使用动态内存分配（例如 malloc），需要释放 phead 指向的节点的内存，以避免内存泄漏。

1. //出队---队头
2. void QueuePop(Queue* pq)
3. {
4. assert(!QueueEmpty(pq));
5. //只有一个结点的情况
6. if (pq->phead == pq->ptail)
7. {
8. free(pq->phead);
9. pq->phead = pq->ptail = NULL;
10. }
11. else {
12. QueueNode* next = pq->phead->next;
13. free(pq->phead);
14. pq->phead = next;
15. }
16. pq->size--;
17. }

复制代码

3.3 取队头数据

在确定队列不为空的情况下，取队头数据非常简单。

1. 检查队列是否为空：

   在访问队头元素之前，我们需要检查队列是否为空。如果队列为空（即 phead == NULL），表示没有元素可以访问，此时应返回一个错误信息或者错误值。

2. 访问队头数据：

   如果队列不为空，可以直接访问 phead 节点的数据。队列的头部数据就是 phead->data。

3. 返回队头数据：

   返回 phead 节点中的数据，这个数据是队列头部的元素，且队列结构不发生变化。

1. //取队头数据
2. QDataTpe QueueFront(Queue* pq)
3. {
4. assert(!QueueEmpty(pq));
5. return pq->phead->data;
6. }

复制代码

3.4 取队尾数据

1. 检查队列是否为空：

   在访问队尾元素之前，我们需要检查队列是否为空。如果队列为空（即 ptail == NULL），表示没有元素可以访问，此时应返回一个错误信息或者错误值。

2. 访问队尾数据：

   如果队列不为空，可以直接访问 rear 节点的数据。队列的尾部数据就是 ptail->data。

3. 返回队尾数据：

   返回 ptail 节点中的数据，这个数据是队列尾部的元素，且队列结构不发生变化。

1. QDataTpe QueueBack(Queue* pq)
2. {
3. assert(!QueueEmpty(pq));
4. return pq->ptail->data;
5. }

复制代码

3.5 队列有效元素个数

通常情况下，使用计数器（方法一）更加高效，即在每次入队列和出队列时，都会对pq->size进行改变，  在入队列时则   pq->size++，在出队列时则 pq->size--。

这使我们可以直接得出队列的有效元素个数，避免了遍历链表（这种方法在计算队列大小时需要遍历整个链表，因此时间复杂度是 O(n)。在每次查询时，性能较差）。

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

复制代码

完整代码：

Queue.h：

1. #pragma once
2. #include<stdio.h>
3. #include<stdlib.h>
4. #include<assert.h>
5. #include<stdbool.h>
7. //定义结点的结构
8. typedef int QDataTpe;
9. typedef struct QueueNode
10. {
11. QDataTpe data;
12. struct QueueNode* next;
13. }QueueNode;
15. //定义队列的结构
16. typedef struct Queue {
17. QueueNode* phead;//队头
18. QueueNode* ptail;//队尾
19. int size;//记录有效数据个数
20. }Queue;
22. void QueueInit(Queue* pq);
23. //销毁队列
24. void QueueDestroy(Queue* pq);
26. //入队---队尾
27. void QueuePush(Queue* pq, QDataTpe x);
28. //出队---队头
29. void QueuePop(Queue* pq);
31. //取队头数据
32. QDataTpe QueueFront(Queue* pq);
33. //取队尾数据
34. QDataTpe QueueBack(Queue* pq);
36. bool QueueEmpty(Queue* pq);
37. //队列有效元素个数
38. int QueueSize(Queue* pq);

复制代码

Queue.c：

1. #include"Queue.h"
3. void QueueInit(Queue* pq)
4. {
5. assert(pq);
6. pq->phead = pq->ptail = NULL;
7. }
8. //销毁队列
9. void QueueDestroy(Queue* pq)
10. {
11. assert(pq);
12. QueueNode* pcur = pq->phead;
13. while (pcur)
14. {
15. QueueNode* next = pcur->next;
16. free(pcur);
17. pcur = next;
18. }
19. pq->phead = pq->ptail = NULL;
20. }
21. //入队---队尾
22. void QueuePush(Queue* pq, QDataTpe x)
23. {
24. assert(pq);
25. //newnode
26. QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));
27. if (newnode == NULL)
28. {
29. perror("malloc fail!");
30. exit(1);
31. }
32. newnode->data = x;
33. newnode->next = NULL;
35. //队列为空，newnode是队头也是队尾
36. if (pq->phead == NULL)
37. {
38. pq->phead = pq->ptail = newnode;
39. }
40. else {
41. //队列非空，直接插入到队尾
42. pq->ptail->next = newnode;
43. pq->ptail = pq->ptail->next;
44. }
45. pq->size++;
46. }
47. bool QueueEmpty(Queue* pq)
48. {
49. assert(pq);
50. return pq->phead == 0;
51. }
52. //出队---队头
53. void QueuePop(Queue* pq)
54. {
55. assert(!QueueEmpty(pq));
56. //只有一个结点的情况
57. if (pq->phead == pq->ptail)
58. {
59. free(pq->phead);
60. pq->phead = pq->ptail = NULL;
61. }
62. else {
63. QueueNode* next = pq->phead->next;
64. free(pq->phead);
65. pq->phead = next;
66. }
67. pq->size--;
68. }
69. //取队头数据
70. QDataTpe QueueFront(Queue* pq)
71. {
72. assert(!QueueEmpty(pq));
73. return pq->phead->data;
74. }
75. //取队尾数据
76. QDataTpe QueueBack(Queue* pq)
77. {
78. assert(!QueueEmpty(pq));
79. return pq->ptail->data;
80. }
82. //队列有效元素个数
83. int QueueSize(Queue* pq)
84. {
85. return pq->size;
86. }

复制代码

以上为队列结构的介绍，感谢敢看！