备案控制台
开发者社区 云计算 文章 正文

【数据结构】队列-C语言版

2023-02-07 61
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： 【数据结构】队列-C语言版

队列的概念

队列：只允许在一端插入数据，在另一端删除数据的特殊线性表，队列具有先进先出（First In First Out）的性质

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

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

可以使用数组和链表的结构实现队列，使用链表的结构实现更优一些，因为如果使用数组的结构实现队列，那么删除数据在队头进行，效率比较低，队列为空时，front=rear=NULL。


队列的实现

头文件  040-Queue.h

1. #pragma once
2. #include<stdio.h>
3. #include<stdbool.h>
4. #include<assert.h>
5. #include<stdlib.h>
6. 
7. typedef int QDataType;
8. typedef struct QueueNode
9. {
10.   struct QueueNode* next;
11.   QDataType data;
12. }QueueNode;
13. 
14. typedef struct Queue
15. {
16.   QueueNode* head;
17.   QueueNode* tail;
18. }Queue;
19. 
20. //初始化
21. void QueueInit(Queue* pq);
22. 
23. //销毁
24. void QueueDestroy(Queue* pq);
25. 
26. //插入数据
27. void QueuePush(Queue* pq, QDataType x);
28. 
29. //删除数据
30. void QueuePop(Queue* pq);
31. 
32. //取队头数据
33. QDataType QueueFront(Queue* pq);
34. 
35. //取队尾数据
36. QDataType QueueRear(Queue* pq);
37. 
38. //判断队是否已满
39. bool QueueEmpty(Queue* pq);
40. 
41. //求队列元素个数
42. int QueueSize(Queue* pq);

源文件 040-Queue.c

1. #define  _CRT_SECURE_NO_WARNINGS  1
2. #include "040-Queue.h"
3. 
4. //初始化
5. void QueueInit(Queue* pq)
6. {
7.  pq->head = pq->tail = NULL;
8. }
9. 
10. //销毁
11. void QueueDestroy(Queue* pq)
12. {
13.   QueueNode* cur = pq->head;
14.   while (cur)
15.   {
16.     QueueNode* next = cur->next;
17.     free(cur);
18.     cur = next;
19.   }
20.   pq->head = pq->tail = NULL;
21. }
22. 
23. //插入数据
24. void QueuePush(Queue* pq, QDataType x)
25. {
26.   assert(pq);
27.   QueueNode* newNode = (QueueNode*)malloc(sizeof(QueueNode));
28.   if (newNode == NULL)
29.   {
30.     printf("malloc fail\n");
31.     exit(-1);
32.   }
33. 
34.   newNode->data = x;
35.   newNode->next = NULL;
36. 
37.   //插入一个数据，尾指针+1，当尾指针为空时，队列为空
38.   if (pq->tail == NULL)
39.   {
40.     pq->head = pq->tail = newNode;
41.   }
42.   else
43.   {
44.     pq->tail->next = newNode;
45.     pq->tail = newNode;
46.   }
47. }
48. 
49. //删除数据
50. void QueuePop(Queue* pq)
51. {
52.   assert(pq);
53.   assert(!QueueEmpty(pq));
54.   if (pq->head->next == NULL)
55.   {
56.     free(pq->head);
57.     pq->head = pq->tail = NULL;
58.   }
59.   else
60.   {
61.     QueueNode* next = pq->head->next;
62.     free(pq->head);
63.     pq->head = next;
64.   }
65. }
66. 
67. //取队头数据
68. QDataType QueueFront(Queue* pq)
69. {
70.   assert(pq);
71.   assert(!QueueEmpty(pq));
72. 
73.   return pq->head->data;
74. }
75. 
76. //取队尾数据
77. QDataType QueueRear(Queue* pq)
78. {
79.   assert(pq);
80.   assert(!QueueEmpty(pq));
81. 
82.   return pq->tail->data;
83. }
84. 
85. //判断队是否已满
86. bool QueueEmpty(Queue* pq)
87. {
88.   assert(pq);
89. 
90.   return pq->head == NULL;
91. }
92. 
93. //求队列元素个数
94. int QueueSize(Queue* pq)
95. {
96. 
97.   int size = 0;
98.   QueueNode* cur = pq->head;
99.   while (cur)
100.  {
101.    size++;
102.    cur = cur->next;
103.  }
104.  return size;
105. 
106. }

测试文件 040-test.c

1. #define  _CRT_SECURE_NO_WARNINGS  1
2. #include"040-Queue.h"
3. void TestQueue()
4. {
5.  Queue q;
6.  QueueInit(&q);
7.  QueuePush(&q, 1);
8.  QueuePush(&q, 2);
9. 
10.   printf("%d ", QueueFront(&q));
11.   QueuePop(&q);
12. 
13.   printf("%d ", QueueFront(&q));
14.   QueuePop(&q);
15. 
16.   QueuePush(&q, 3);
17.   QueuePush(&q, 4);
18. 
19.   while (!QueueEmpty(&q))
20.   {
21.     printf("%d ", QueueFront(&q));
22.     QueuePop(&q);
23.   }
24. 
25.   printf("\n");
26. 
27.   QueueDestroy(&q);
28. }
29. 
30. int main()
31. {
32.   TestQueue();
33. }


队列的应用

1.用两个队列实现一个栈  OJ链接

分析：栈的性质是后进先出，如先后入栈1,2,3,4，可以依次将其入到A队列中，如要4出队列，可以先将1,2,3放入B队列，返回A队列中的4。始终保持一个队列为空，一个队列不为空。

再入数据就入到不为空的队列里。

1. typedef int QDataType;
2. typedef struct QueueNode
3. {
4.     struct QueueNode* next;
5.     QDataType data;
6. }QueueNode;
7. 
8. typedef struct Queue
9. {
10.     QueueNode* head;
11.     QueueNode* tail;
12. }Queue;
13. 
14. //初始化
15. void QueueInit(Queue* pq);
16. 
17. //销毁
18. void QueueDestroy(Queue* pq);
19. 
20. //插入数据
21. void QueuePush(Queue* pq, QDataType x);
22. 
23. //删除数据
24. void QueuePop(Queue* pq);
25. 
26. //取队头数据
27. QDataType QueueFront(Queue* pq);
28. 
29. //取队尾数据
30. QDataType QueueRear(Queue* pq);
31. 
32. //判断队是否已满
33. bool QueueEmpty(Queue* pq);
34. 
35. //求队列元素个数
36. int QueueSize(Queue* pq);
37. 
38. //初始化
39. void QueueInit(Queue* pq)
40. {
41.     pq->head = pq->tail = NULL;
42. }
43. 
44. //销毁
45. void QueueDestroy(Queue* pq)
46. {
47.     QueueNode* cur = pq->head;
48.     while (cur)
49.     {
50.         QueueNode* next = cur->next;
51.         free(cur);
52.         cur = next;
53.     }
54.     pq->head = pq->tail = NULL;
55. }
56. 
57. //插入数据
58. void QueuePush(Queue* pq, QDataType x)
59. {
60.     assert(pq);
61.     QueueNode* newNode = (QueueNode*)malloc(sizeof(QueueNode));
62.     if (newNode == NULL)
63.     {
64.         printf("malloc fail\n");
65.         exit(-1);
66.     }
67. 
68.     newNode->data = x;
69.     newNode->next = NULL;
70. 
71.     //插入一个数据，尾指针+1，当尾指针为空时，队列为空
72.     if (pq->tail == NULL)
73.     {
74.         pq->head = pq->tail = newNode;
75.     }
76.     else
77.     {
78.         pq->tail->next = newNode;
79.         pq->tail = newNode;
80.     }
81. }
82. 
83. //删除数据
84. void QueuePop(Queue* pq)
85. {
86.     assert(pq);
87.     assert(!QueueEmpty(pq));
88.     if (pq->head->next == NULL)
89.     {
90.         free(pq->head);
91.         pq->head = pq->tail = NULL;
92.     }
93.     else
94.     {
95.         QueueNode* next = pq->head->next;
96.         free(pq->head);
97.         pq->head = next;
98.     }
99. }
100. 
101. //取队头数据
102. QDataType QueueFront(Queue* pq)
103. {
104.     assert(pq);
105.     assert(!QueueEmpty(pq));
106.     
107.     return pq->head->data;
108. }
109. 
110. //取队尾数据
111. QDataType QueueRear(Queue* pq)
112. {
113.     assert(pq);
114.     assert(!QueueEmpty(pq));
115.     
116.     return pq->tail->data;
117. }
118. 
119. //判断队是否已满
120. bool QueueEmpty(Queue* pq)
121. {
122.     assert(pq);
123.     
124.     return pq->head == NULL;
125. }
126. 
127. //求队列元素个数
128. int QueueSize(Queue* pq)
129. {
130.     
131.     int size = 0;
132.     QueueNode* cur = pq->head;
133.     while (cur)
134.     {
135.         size++;
136.         cur = cur->next;
137.     }
138.     return size;
139.     
140. }
141. 
142. typedef int STDataType;
143. typedef struct {
144.     Queue q1;
145.     Queue q2;
146. } MyStack;
147. 
148. //建栈
149. MyStack* myStackCreate() {
150. 
151.     //不能这么写,return的是地址，除了函数st变量就销毁了，可以用malloc，在return 之后再free
152.     //MyStack* st;
153.     //return &st;
154.     MyStack* obj = (MyStack*)malloc(sizeof(MyStack));
155.     QueueInit(&obj->q1);
156.     QueueInit(&obj->q2);
157.     return obj;
158. }
159. 
160. //入队
161. void myStackPush(MyStack* obj, int x) {
162.     if(!QueueEmpty(&obj->q1))
163.     {
164.         QueuePush(&obj->q1,x);
165.     }
166.     else
167.     {
168.         QueuePush(&obj->q2,x);
169.     }   
170. }
171. 
172. //删除栈顶元素
173. int myStackPop(MyStack* obj) {
174.     Queue* pEmpty = &obj->q1;
175.     Queue* pNonoEmpty = &obj->q2;
176.     if(!QueueEmpty(&obj->q1))
177.     {
178.         pEmpty = &obj->q2;
179.         pNonoEmpty = &obj->q1;
180.     }
181.     while(QueueSize(pNonoEmpty)>1)
182.     {
183.         QueuePush(pEmpty,QueueFront(pNonoEmpty));
184.         QueuePop(pNonoEmpty);
185.     }
186.     int front = QueueFront(pNonoEmpty);
187.     QueuePop(pNonoEmpty);
188.     return front;
189. }
190. 
191. //返回栈顶元素
192. int myStackTop(MyStack* obj) {
193.     if(!QueueEmpty(&obj->q1))
194.     {
195.         return QueueRear(&obj->q1);
196.     }
197.     else
198.     {
199.         return QueueRear(&obj->q2);
200.     }
201. }
202. 
203. //判空
204. bool myStackEmpty(MyStack* obj) {
205.     return QueueEmpty(&obj->q1) && QueueEmpty(&obj->q2);
206. }
207. 
208. //释放栈
209. void myStackFree(MyStack* obj) {
210.     QueueDestroy(&obj->q1);
211.     QueueDestroy(&obj->q2);
212.     free(obj);
213. }

2.用两个栈实现一个队列  OJ链接

分析：用两个栈实现队列，队列先进先出，如入队1，2，3，4，将其依次入到A栈，要出队，就要先出1，此时可以将2，3，4入栈到B栈，A栈中只留下1，1就可以从A栈出了。

如果再要出数据，可以从非空栈中出，

要入数据就入到空栈中，如入5 6 7，

因此可以固定从A入，从B出，如果B不为空，就从B出数据，如果B为空，就把A的数据依次入到B中。

1. typedef int STDataType;
2. struct Stack
3. {
4.     STDataType* a;
5.     int top;//栈顶，指向最后一个元素的下一个位置
6.     int capacity;//容量，方便增容
7. };
8. 
9. typedef struct Stack Stack;
10. 
11. //初始化
12. void StackInit(Stack* pst);
13. 
14. //销毁
15. void StackDestroy(Stack* pst);
16. 
17. //栈的性质就决定了只能在栈顶出入数据
18. //插入元素
19. void StackPush(Stack* pst, STDataType x);
20. 
21. //删除元素
22. void StackPop(Stack* pst);
23. 
24. //返回栈顶元素
25. STDataType StackTop(Stack* pst);
26. 
27. //判断栈是否已满，空返回1，非空返回0
28. bool StackEmpty(Stack* pst);
29. 
30. //求栈中元素个数
31. int StackSize(Stack* pst);
32. 
33. //初始化
34. void StackInit(Stack* pst)
35. {
36.     assert(pst);
37.     pst->a = (STDataType*)malloc(sizeof(STDataType) * 4);
38.     pst->top = 0;
39.     pst->capacity = 4;
40. }
41. 
42. //销毁
43. void StackDestroy(Stack* pst)
44. {
45.     assert(pst);
46.     free(pst->a);
47.     pst->a = NULL;
48.     pst->capacity = pst->top = 0;
49. }
50. 
51. //插入元素
52. void StackPush(Stack* pst, STDataType x)
53. {
54.     if (pst->top == pst->capacity)
55.     {
56.         STDataType* tmp = (STDataType*)realloc(pst->a, sizeof(STDataType) * pst->capacity * 2);
57.         if (tmp == NULL)
58.         {
59.             printf("realloc fail\n");
60.             exit(-1);
61.         }
62.         pst->a = tmp;
63.         pst->capacity *= 2;
64.     }
65. 
66.     pst->a[pst->top] = x;
67.     pst->top++;
68. }
69. 
70. //删除元素
71. void StackPop(Stack* pst)
72. {
73.     assert(pst);
74.     assert(!StackEmpty(pst));
75.     pst->top--;
76. }
77. 
78. //返回栈顶元素
79. STDataType StackTop(Stack* pst)
80. {
81.     assert(pst);
82.     assert(!StackEmpty(pst));
83. 
84.     return pst->a[pst->top - 1];
85. }
86. 
87. //判断栈是否已满，空返回1，非空返回0
88. bool StackEmpty(Stack* pst)
89. {
90.     assert(pst);
91.     return pst->top == 0;
92. }
93. 
94. //求栈中元素个数
95. int StackSize(Stack* pst)
96. {
97.     assert(pst);
98.     return pst->top;
99. }
100. 
101. typedef struct {
102.     Stack s1;
103.     Stack s2;
104. } MyQueue;
105. 
106. //创建队列
107. MyQueue* myQueueCreate() {
108.     MyQueue* obj = (MyQueue*)malloc(sizeof(MyQueue));
109.     StackInit(&obj->s1);
110.     StackInit(&obj->s2);
111. 
112.     return obj;
113. }
114. 
115. //入队
116. void myQueuePush(MyQueue* obj, int x) {
117.    
118.     StackPush(&obj->s1,x);
119.     
120. }
121. 
122. //返回队头元素
123. int myQueuePeek(MyQueue* obj) {
124.     if(StackEmpty(&obj->s2))//s2为空，就把元素全部入到s2中
125.     {
126.         while(!StackEmpty(&obj->s1))
127.         {
128.             StackPush(&obj->s2,StackTop(&obj->s1));
129.             StackPop(&obj->s1);           
130.         }        
131.     }
132.     return StackTop(&obj->s2);//s2顶部元素就是队头元素
133. }
134. 
135. //删除队头元素
136. int myQueuePop(MyQueue* obj) {
137.     int ret = myQueuePeek(obj);  //这里要传obj
138.     StackPop(&obj->s2);
139.     return ret;
140.     
141. }
142. 
143. //判断队空
144. bool myQueueEmpty(MyQueue* obj) {
145.     return StackEmpty(&obj->s1) && StackEmpty(&obj->s2);
146. }
147. 
148. //释放队列
149. void myQueueFree(MyQueue* obj) {
150.     StackDestroy(&obj->s1);
151.     StackDestroy(&obj->s2);
152.     free(obj);
153.     obj = NULL;
154. }

3.设计循环队列  OJ链接

分析：循环队列和普通队列区别在于：

循环队列如何判空和判断满了？因为空的时候front和tail指向同一个节点，满的时候，front和tail也指向同一个节点。可以空出一个节点不存储数据，当front=tail时队空，当tail的下一个为front时，队满。

1. #define  _CRT_SECURE_NO_WARNINGS  1
2. typedef struct {
3.  int* a;
4.  int k;
5.  int front;
6.  int tail;
7. }MyCircularQueue;
8. 
9. //创建队列
10. MyCircularQueue* myCircularQueueCreate(int k) {
11.   MyCircularQueue* obj = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));
12.   obj->a = (int*)malloc(sizeof(int) * (k + 1));
13.   obj->k = k;
14.   obj->front = 0;
15.   obj->tail = 0;
16.   return obj;
17. }
18. 
19. //判断队满
20. bool myCircularQueueIsFull(MyCircularQueue* obj) {
21.   int tailNext = obj->tail + 1;
22.   if (tailNext == obj->k + 1)
23.   {
24.     tailNext = 0;
25.   }
26.   return tailNext == obj->front;
27. }
28. 
29. //入队
30. bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
31.   if (myCircularQueueIsFull(obj))
32.   {
33.     return false;
34.   }
35.   else
36.   {
37.     obj->a[obj->tail] = value;
38.     obj->tail++;
39. 
40.     obj->tail  %= (obj->k + 1);
41. 
42.     return true;
43.   }
44. 
45. }
46. 
47. //判断队空
48. bool myCircularQueueIsEmpty(MyCircularQueue* obj) {
49.   return obj->front == obj->tail;
50. }
51. 
52. bool myCircularQueueDeQueue(MyCircularQueue* obj) {
53.   if (myCircularQueueIsEmpty(obj))
54.   {
55.         return false;
56.   }
57.   else
58.   {
59.     obj->front++;
60.     if (obj->front == obj->k + 1)
61.     {
62.       obj->front = 0;
63.     }
64.         return true;
65.   }
66. }
67. 
68. //返回队头元素
69. int myCircularQueueFront(MyCircularQueue* obj) {
70.     //printf("%d",myCircularQueueIsEmpty(obj));
71. 
72.     if(myCircularQueueIsEmpty(obj))
73.     {
74.         return -1;
75.     }
76.   return obj->a[obj->front];
77. }
78. 
79. //返回队尾元素
80. int myCircularQueueRear(MyCircularQueue* obj) {
81.     if(myCircularQueueIsEmpty(obj))
82.     {
83.         return -1;
84.     }
85.   int tailPrev = obj->tail - 1;//tail指向最后一个元素的下一个位置，最后一个元素的位置是tail-1
86.   if (tailPrev == -1)
87.   {
88.     tailPrev = obj->k;
89.   }
90.   return obj->a[tailPrev];
91. }
92. 
93. //释放队列
94. void myCircularQueueFree(MyCircularQueue* obj) {
95.   free(obj->a);
96.     free(obj);
97. }


文章标签：
存储
关键词：
C语言数据结构
数据结构c语言
数据结构队列
C语言队列
数据结构队列C语言
玲娜贝儿～
目录
相关文章
倔强的石头_
|
2天前
|
算法 C语言
【数据结构与算法 经典例题】使用栈实现队列（图文详解）
【数据结构与算法 经典例题】使用栈实现队列（图文详解）
倔强的石头_
10 0
倔强的石头_
|
3天前
|
存储 缓存 前端开发
【数据结构/C语言】深入理解 双向链表
【数据结构/C语言】深入理解 双向链表
倔强的石头_
13 0
反季雪
|
3天前
|
存储 算法
【数据结构和算法】--队列的特殊结构-循环队列
【数据结构和算法】--队列的特殊结构-循环队列
反季雪
6 0
lge101058
|
3天前
|
存储 测试技术
【数据结构】操作受限的线性表，队列的具体实现
【数据结构】操作受限的线性表，队列的具体实现
lge101058
14 4
倔强的石头_
|
2天前
|
算法 C语言
【数据结构与算法 经典例题】使用队列实现栈（图文详解）
【数据结构与算法 经典例题】使用队列实现栈（图文详解）
倔强的石头_
11 1
米诺斯
|
1天前
|
存储 编译器 C语言
C语言的联合体：一种节省内存的数据结构
C语言的联合体：一种节省内存的数据结构
米诺斯
6 0
枫叶丹4
|
2天前
【海贼王的数据航海】栈和队列
【海贼王的数据航海】栈和队列
枫叶丹4
4 0
反季雪
|
2天前
|
存储 算法 搜索推荐
【数据结构和算法】--- 基于c语言排序算法的实现（2）
【数据结构和算法】--- 基于c语言排序算法的实现（2）
反季雪
4 0
倔强的石头_
|
3天前
|
算法 程序员 数据处理
【数据结构与算法】使用单链表实现队列：原理、步骤与应用
【数据结构与算法】使用单链表实现队列：原理、步骤与应用
倔强的石头_
8 0
反季雪
|
3天前
|
搜索推荐 算法 C语言
【数据结构和算法】--- 基于c语言排序算法的实现（1）
【数据结构和算法】--- 基于c语言排序算法的实现（1）
反季雪
12 0

热门文章

最新文章

  • 1
    云原生数据仓库产品使用合集之在ADB中，如何将源数据的多表（数据结构一致）汇总到一张表
  • 2
    InfluxDB数据模型与数据结构设计详解
  • 3
    可视化数据结构——让你的树跃然纸上
  • 4
    【C 言专栏】C 语言中的数据结构应用
  • 5
    栈数据结构详解
  • 6
    22个常用数据结构实现与原理分析
  • 7
    数据结构面试常见问题
  • 8
    数据结构第二课 -----线性表之顺序表
  • 9
    【数据结构】哈夫曼树编译码器【课程设计】
  • 10
    数据结构——lesson12排序之归并排序
  • 1
    Redis数据类型详解：选择合适的数据结构优化你的应用
    78
  • 2
    【算法与数据结构】二叉树（前中后）序遍历2
    24
  • 3
    【MongoDB】MongoDB 如何处理复杂的数据结构？
    39
  • 4
    【数据结构】排序算法
    35
  • 5
    【数据结构】C语言实现链队列(附完整运行代码)
    54
  • 6
    深入理解InnoDB索引数据结构和算法
    75
  • 7
    【数据结构】深入浅出理解链表中二级指针的应用
    45
  • 8
    【数据结构】线性表的链式存储结构
    29
  • 9
    【数据结构】C语言实现顺序表万字详解(附完整运行代码)
    52
  • 10
    【Redis技术进阶之路】「底层源码解析」揭秘高效存储模型与数据结构底层实现（字典）（二）
    75

    • 相关课程

    更多
  • Go语言核心编程 - 数据结构和算法
  • 你的第一门C语言课
  • C语言学习教程
  • Go语言核心编程 - 基础语法、数组、切片、Map

    • 相关电子书

    更多
  • 如何使用Tair增强数据结构构建丰富在线实时场景
  • Apache Flink 流式应用中状态的数据结构定义升级
  • 低代码开发师（初级）实战教程
    • 下一篇
    部署LAMP环境（Alibaba Cloud Linux 3）