数据结构之顺序队列

数据结构之队列

什么是队列

• 队列是和栈一样操作受限的线性表，栈是只允许在线性表的一端进行入栈和出栈操作，而队列是会允许在线性表的一端进行入队，在另外一端进行出队操作

队列的基本操作

1. bool initQueue(Queue & Q); // 初始化队列
2. void destroyQueue(Queue Q); // 如果是顺序队列则不需要销毁
3. bool push(Queue & Q, ElemType x); // 入队
4. bool pop(Queue & Q, ElemType & x); // 出队
5. // 获取队头元素的值
6. void getTop(Queue Q, ELemType & x);
7. bool queueEmpty(Queue Q); // 判断队列是否为空

复制代码

顺序队列

• 用静态数组实现的队列（使用顺序存储结构实现的队列）缺点：空间固定
  
  

顺序队列的代码实现

1. #include<stdio.h>
2. #define Elemtype int
3. #define MaxSize 10
4. typedef struct SQueue{
5. Elemtype data[MaxSize];
6. size_t front,rear; // 队头和队尾指针（存储数组下标）
7. }SQueue;
8. bool initQueue(SQueue & Q)
9. {
10. Q.front = 0;
11. Q.rear = 0;
12. }
13. // 入队
14. bool push(Queue & Q, ElemType x)
15. {
16. // 如果队列满了则返回false
17. if((Q.rear + 1) % MaxSize == Q.front)
18. return false;
19. Q.data[Q.rear] = x;
20. Q.rear = (Q.rear+1) % MaxSize;
21. }
22. // 出队
23. bool pop(Queue & Q, ElemType & x)
24. {
25. // 如果队列为空，则返回false
26. if(Q.front == Q.rear)
27. return false
28. x = Q.data[Q.front];
29. Q.front = (Q.front + 1) % MaxSize;
30. }
31. // 获取队头元素的值
32. void getTop(Queue Q, ELemType & x){
33. // 如果队列为空，则返回false
34. if(Q.front == Q.rear)
35. return false
36. x = Q.data[Q.front];
37. }
38. // 判断队列是否为空
39. bool SqueueEmpty(SQueue Q);{
40. if(Q.front == Q.rear)
41. return true;
42. return false;
43. }

复制代码

代码缺陷

上述代码实现的队列，会浪费一个存储空间，如何避免浪费一个存储空间呢？

1. 使用一个length变量，存储队列的长度

1. typedef struct SQueue{
2. Elemtype data[MaxSize];
3. size_t front,rear; // 队头和队尾指针（存储数组下标）
4. Size_t length;
5. }SQueue;
6. bool initQueue(SQueue & Q)
7. {
8. Q.front = 0;
9. Q.rear = 0;
10. Q.length = 0; // 计数器
11. }
12. // 入队
13. bool push(Queue & Q, ElemType x)
14. {
15. // 如果队列满了则返回false
16. if(Q.front == Q.rear && Q.length == MaxSize)
17. return false;
18. Q.data[Q.rear] = x;
19. Q.rear = (Q.rear+1) % MaxSize;
20. Q.length++;
21. }
22. // 出队
23. bool pop(Queue & Q, ElemType & x)
24. {
25. // 如果队列为空，则返回false
26. if(Q.front == Q.rear && Q.length == 0)
27. return false
28. x = Q.data[Q.front];
29. Q.front = (Q.front + 1) % MaxSize;
30. Q.rear--;
31. }

复制代码

2. 使用一个flag变量，出队时将flag 置为0 ， 入队将flag置为1

1. typedef struct SQueue{
2. Elemtype data[MaxSize];
3. size_t front,rear; // 队头和队尾指针（存储数组下标）
4. bool flag;
5. }SQueue;
6. bool initQueue(SQueue & Q)
7. {
8. Q.front = 0;
9. Q.rear = 0;
10. }
11. // 入队
12. bool push(Queue & Q, ElemType x)
13. {
14. // 如果队列满了则返回false
15. if(Q.front == Q.rear && Q.flag = 1)
16. return false;
17. Q.data[Q.rear] = x;
18. Q.rear = (Q.rear+1) % MaxSize;
19. Q.flag = 1;
20. }
21. // 出队
22. bool pop(Queue & Q, ElemType & x)
23. {
24. // 如果队列为空，则返回false
25. if(Q.front == Q.rear && Q.flag == 0)
26. return false
27. x = Q.data[Q.front];
28. Q.front = (Q.front + 1) % MaxSize;
29. Q.rear--;
30. Q.flat = 0;
31. }

复制代码

链式队列

• 用链表实现的队列（存储空间不固定，根据内存来确定）

1. #include<stdio.h>
2. #include<stdlib.h>
3. #define ElemType int
5. typedef struct LinkNode { // 链式队列结点
6. ElemType data;
7. struct LinkNode* next;
8. }LinkNode;
10. typedef struct {
11. LinkNode* front, * rear; // 队列的队头和队尾指针
12. }LinkQueue;
14. // 初始化链式队列
15. bool initLinkQueue(LinkQueue& LQ)
16. {
17. LinkNode* n = (LinkNode*)malloc(sizeof(LinkNode));
18. if (n == NULL)
19. return false;
20. n->next = NULL;
21. LQ.front = n;
22. LQ.rear = n;
23. return true;
24. }
25. // 销毁链式队列
26. void destoryQueue(LinkQueue& LQ)
27. {
28. LinkNode* cur = LQ.front->next;
29. LinkNode* next;
30. while (cur != NULL)
31. {
32. next = cur->next;
33. free(cur);
34. cur = next;
35. }
36. free(LQ.front); // 释放头结点
37. LQ.front = NULL;
38. LQ.rear = NULL;
39. }
40. // 判断链式队列为空
41. bool isEmpty(LinkQueue LQ)
42. {
43. if (LQ.front == LQ.rear)
44. return true;
45. else
46. return false;
47. }
48. // 入队
49. bool push(LinkQueue& LQ, ElemType x)
50. {
51. LinkNode* n = (LinkNode*)malloc(sizeof(LinkNode));
52. if (n == NULL)
53. return false;
54. n->data = x;
55. n->next = NULL;
56. LQ.rear->next = n;
57. LQ.rear = n; // 修改队尾指针
58. return true;
59. }
60. // 出队
61. bool pop(LinkQueue& LQ, ElemType& x)
62. {
63. if (isEmpty(LQ)) // 判断链式队列是否为空
64. return false;
65. LinkNode* head = LQ.front;
66. LinkNode* cur = head->next; // 当前要出的结点
67. x = cur->data;
68. head->next = cur->next;
69. if (LQ.rear == cur) // 此次出队的是最后一个结点
70. LQ.rear = LQ.front;
71. free(cur); // 释放结点
72. return true;
73. }
74. // 获取队头结点存放的数据
75. bool getTop(LinkQueue& LQ, ElemType& x)
76. {
77. if (isEmpty(LQ)) // 判断链式队列是否为空
78. return false;
79. LinkNode* head = LQ.front;
80. LinkNode* cur = head->next; // 队头结点
81. x = cur->data;
82. return true;
83. }
84. // 打印整个队列
85. void printQueue(LinkQueue LQ)
86. {
87. LinkNode* cur = LQ.front->next; // 作为遍历整个队列的结点
88. if(!isEmpty(LQ))
89. {
90. while (cur != NULL)
91. {
92. printf("%d <- ", cur->data);
93. cur = cur->next;
94. }
95. printf("NULL\n");
96. }
97. }
99. // 测试函数
100. void test_LinkQueue(){
101. LinkQueue LQ;
102. initLinkQueue(LQ);
103. push(LQ, 1);
104. push(LQ, 2);
105. push(LQ, 3);
106. push(LQ, 4);
107. printQueue(LQ);
108. ElemType x = 0;
109. pop(LQ, x);
110. pop(LQ, x);
112. printQueue(LQ);
114. }
116. int main()
117. {
118. test_LinkQueue();
119. return 0;
120. }

复制代码

队列的变种（双端队列）

双端队列：受限制的线性表，可以在线性表的两端进行插入和删除操作

1. 双端队列只允许在队列的一端进行插入和删除操作就等价于栈
2. 输入受限的双端队列: 只允许一端进行插入，两端允许删除的线性表
3. 输出受限的双端队列: 只允许一段进行删除，两段允许插入的线性表

练习题：判断输出序列合法性

若数据元素输入序列为1,2,3,4,5 则哪些输出序列是合法的，哪些是非法的？

来源：程序园用户自行投稿发布，如果侵权，请联系站长删除
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！