线性结构常见应用之队列[基于郝斌课程]

定义：
  一种可以实现“先进先出”的存储结构
  队列类似于排队买票
分类：
  链式队列：基于列表
  静态队列：基于数组
    静态队列通常都必须是循环队列
      静态队列为什么是循环队列？
        减少对内存的浪费
        用传统数组来实现队列的话，参数只能加不能减
      循环队列需要几个参数来确定以及各个参数的含义
        需要两个参数来确定：front 和 rear
        两个参数不同场合有不同的含义
          队列初始化： front 和 rear 都是0
          队列非空：front 代表的是队列的第一个元素， rear 代表的是队列的最后一个有效元素的下一个元素
          队列空：front 和 rear 是相等的，但是不一致是0
      循环队列的入队伪算法
        rear = (rear + 1) % 数组的长度
      循环队列的出队伪算法
        front = (front + 1) % 数组的长度
      如何判断循环队列是否为空？
        如果 front == rear，则队列为空
      如何判断循环队列是否已满？
       front 和 rear 大小没有规律，可以 front 比 rear 大，也可以是 front 比 rear 小 
       规定放入的元素比数组长度少1，只要 rear 和 front 相邻，则满了
       如果 ((rear + 1) % 数组长度) == front，则队列满了
队列的应用：
  所有和时间有关的操作都与队列有关

1. /*
2. @file      main.c
3. @brief     线性结构常见应用之队列
4. @author    EricsT (EricsT@163.com)
5. @version   v1.0.0
6. @date      2025-09-24
7. @history   2025-09-24 EricsT - 新建文件
8. */
10. #include <stdio.h>
11. #include <malloc.h>
13. #define LEN 6
15. typedef struct QUEUE
16. {
17.         int* pBase;
18.         int front;
19.         int rear;
20. }Queue, *PtrQueue;
23. void InitQueue(PtrQueue ptrQueue);//初始化
24. bool InQueue(PtrQueue ptrQueue, int inValue);//入队
25. bool OutQueue(PtrQueue ptrQueue);//出队
26. bool isEmptyQueue(const PtrQueue ptrQueue);//判断是否为空
27. bool isFullQueue(const PtrQueue ptrQueue);//判断是否满了
28. void TraverseQueue(const PtrQueue ptrQueue);//遍历
30. int main(void)
31. {
32.         Queue queue;
34.         InitQueue(&queue);
36.         if (isEmptyQueue(&queue))
37.                 printf("队列为空\n");
38.         else
39.                 printf("队列不空\n");
41.         int inVaule;
43.         printf("请输入要入队的值：");
44.         scanf("%d", &inVaule);
45.         InQueue(&queue, inVaule);
47.         printf("请输入要入队的值：");
48.         scanf("%d", &inVaule);
49.         InQueue(&queue, inVaule);
51.         printf("请输入要入队的值：");
52.         scanf("%d", &inVaule);
53.         InQueue(&queue, inVaule);
55.         printf("请输入要入队的值：");
56.         scanf("%d", &inVaule);
57.         InQueue(&queue, inVaule);
59.         printf("请输入要入队的值：");
60.         scanf("%d", &inVaule);
61.         InQueue(&queue, inVaule);
63.         printf("请输入要入队的值：");
64.         scanf("%d", &inVaule);
65.         InQueue(&queue, inVaule);
67.         printf("请输入要入队的值：");
68.         scanf("%d", &inVaule);
69.         InQueue(&queue, inVaule);
71.         if (isEmptyQueue(&queue))
72.                 printf("队列为空\n");
73.         else
74.                 printf("队列不空\n");
76.         if (isFullQueue(&queue))
77.                 printf("队列已满\n");
78.         else
79.                 printf("队列未满\n");
81.         TraverseQueue(&queue);
83.         OutQueue(&queue);
85.         TraverseQueue(&queue);
87.         return 0;
88. }
90. void InitQueue(PtrQueue ptrQueue)
91. {
92.         ptrQueue->pBase = (int*)malloc(sizeof(int) * LEN);
93.         ptrQueue->front = 0;
94.         ptrQueue->rear = 0;
95. }
97. bool InQueue(PtrQueue ptrQueue, int inValue)
98. {
99.         if (isFullQueue(ptrQueue))
100.                 return false;
102.         ptrQueue->pBase[ptrQueue->rear] = inValue;
103.         ptrQueue->rear = (ptrQueue->rear + 1) % LEN;//从后面加入
105.         return true;
106. }
108. bool OutQueue(PtrQueue ptrQueue)
109. {
110.         if (isEmptyQueue(ptrQueue))
111.                 return false;
113.         ptrQueue->front = (ptrQueue->front + 1) % LEN;//先进先出//从前面出去
115.         return true;
116. }
118. bool isEmptyQueue(const PtrQueue ptrQueue)
119. {
120.         if (ptrQueue->front == ptrQueue->rear)
121.                 return true;
123.         return false;
124. }
126. bool isFullQueue(const PtrQueue ptrQueue)
127. {
128.         if (ptrQueue->front == ((ptrQueue->rear + 1) % LEN))
129.                 return true;
131.         return false;
132. }
134. void TraverseQueue(const PtrQueue ptrQueue)
135. {
136.         int i = ptrQueue->front;
138.         while (ptrQueue->rear != i)
139.         {
140.                 printf("%d ", ptrQueue->pBase[i]);
141.                 i = (i + 1) % LEN;
142.         }
144.         printf("\n");
145. }

复制代码

 

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