队列：
只有两个口进出数据，一个专门进入数据，另一个专门出数据，先进先出，FIFO表
一、 顺序队列：
存储元素的连续内存的首地址
容量
队头位置 (出队)
队尾位置 (入队)
[元素数量]
运算：创建、销毁、清空、出队、入队、队空、队满、队头、队尾、元素数量
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#define TYPE int
// 顺序队列结构
typedef struct ArrayQueue
{
TYPE* ptr;
size_t cal; // 容量
size_t front; // 队头位置head\begin
int rear; // 队尾位置tail\back int rear = -1
size_t cnt; // 数量
}ArrayQueue;
// 创建顺序队列
ArrayQueue* create_array_queue(size_t cal)
{
// 申请队列结构内存
ArrayQueue* queue = malloc(sizeof(ArrayQueue));
// 申请存储队列元素的内存
queue->ptr = malloc(sizeof(TYPE)*cal);
// 初始化容量
queue->cal = cal;
queue->front = 0;
queue->rear = -1;
queue->cnt = 0;
return queue;
}
// 销毁
void destroy_array_queue(ArrayQueue* queue)
{
free(queue->ptr);
free(queue);
}
// 队空
bool empty_array_queue(ArrayQueue* queue)
{
return 0 == queue->cnt;
}
// 队满
bool full_array_queue(ArrayQueue* queue)
{
return queue->cal == queue->cnt;
}
// 入队
bool push_array_queue(ArrayQueue* queue,TYPE data)
{
if(full_array_queue(queue)) return false;
queue->rear = (queue->rear+1)%queue->cal;
queue->ptr[queue->rear] = data;
queue->cnt++;
return true;
}
// 出队
bool pop_array_queue(ArrayQueue* queue)
{
if(empty_array_queue(queue)) return false;
queue->front = (queue->front+1)%queue->cal;
queue->cnt--;
return true;
}
// 队头
TYPE head_array_queue(ArrayQueue* queue)
{
return queue->ptr[queue->front];
}
// 队尾
TYPE tail_array_queue(ArrayQueue* queue)
{
return queue->ptr[queue->rear];
}
// 数量
size_t size_array_queue(ArrayQueue* queue)
{
return queue->cnt;
}
int main(int argc,const char* argv[])
{
ArrayQueue* queue = create_array_queue(5);
for(int i=0; i<10; i++)
{
push_array_queue(queue,i+1) && printf("tail:%d size:%d\n",
tail_array_queue(queue),size_array_queue(queue));
}
printf("-----------------\n");
while(!empty_array_queue(queue))
{
printf("front:%d size:%d\n",
head_array_queue(queue),size_array_queue(queue));
pop_array_queue(queue);
}
printf("size=%d\n",size_array_queue(queue));
destroy_array_queue(queue);
queue = NULL;
}
需要注意的问题
1、存储元素是由一维数组+队头位置front+队尾位置rear来表示，入队rear+1,出队front+1，为了让队列能够反复使用，我们需要把一维数组想象成一个环，因此+1后都需要对容量cal求余
front = (front+1)%cal
rear = (rear+1)%cal
2、判断队空和队满问题
如果不处理该问题，那么队空和队满的条件都是 front==rear，就无法区分是队空还是队满
方法1：存储元素的内存多增加一个位置空间(常考)
队空：front==rear
队满：(rear+1)%cal == front
代价：需要额外申请存储一个元素的内存
计算数量：(rear-front+cal)%cal
队尾数据下标：(rear-1+cal)%cal
方法2：顺序队列结构中增加一个记录元素数量的数据项，通过数量与容量对比判断队空、队满
二、
链式队列：
由若干个节点组成的队列结构，只能操作队头节点、队尾节点
链式队列结构：
队头指针
队尾指针
节点数量
运算：创建、销毁、队空、入队、出队、队头、队尾、数量
1 #include <stdio.h>
2 #include <stdlib.h>
3 #include <stdbool.h>
4
5 #define TYPE int
6
7 // 节点结构
8 typedef struct Node
9 {
10 TYPE data;
11 struct Node* next;
12 }Node;
13
14 // 创建节点
15 Node* create_node(TYPE data)
16 {
17 Node* node = malloc(sizeof(Node));
18 node->data = data;
19 node->next = NULL;
20 return node;
21 }
22
23 // 设计链式队列结构
24 typedef struct ListQueue
25 {
26 Node* head; // 队头指针
27 Node* tail; // 队尾指针
28 size_t cnt; // 节点数量
29 }ListQueue;
30
31 // 创建队列
32 ListQueue* create_list_queue(void)
33 {
34 ListQueue* queue = malloc(sizeof(ListQueue));
35 queue->head = NULL;
36 queue->tail = NULL;
37 queue->cnt = 0;
38 return queue;
39 }
40
41
42 // 队空
43 bool empty_list_queue(ListQueue* queue)
44 {
45 return 0 == queue->cnt;
46 }
47
48 // 入队
49 void push_list_queue(ListQueue* queue,TYPE data)
50 {
51 Node* node = create_node(data);
52 if(0 == queue->cnt)
53 {
54 queue->head = node;
55 queue->tail = node;
56 }
57 else
58 {
59 queue->tail->next = node;
60 queue->tail = node;
61 }
62 queue->cnt++;
63 }
64
65 // 出队
66 bool pop_list_queue(ListQueue* queue)
67 {
68 if(empty_list_queue(queue)) return false;
69 Node* temp = queue->head;
70 queue->head = temp->next;
71 free(temp);
72 queue->cnt--;
73 if(0 == queue->cnt) queue->tail = NULL;
74 return true;
75 }
76
77 // 队头
78 TYPE head_list_queue(ListQueue* queue)
79 {
80 return queue->head->data;
81 }
82
83 // 队尾
84 TYPE tail_list_queue(ListQueue* queue)
85 {
86 return queue->tail->data;
87 }
88
89 // 数量
90 size_t size_list_queue(ListQueue* queue)
91 {
92 return queue->cnt;
93 }
94
95 // 销毁队列
96 void destroy_list_queue(ListQueue* queue)
97 {
98 while(pop_list_queue(queue));
99 free(queue);
100 }
101
102 int main(int argc,const char* argv[])
103 {
104 ListQueue* queue = create_list_queue();
105 for(int i=0; i<10; i++)
106 {
107 push_list_queue(queue,i+10);
108 printf("tail:%d,size:%u\n",
109 tail_list_queue(queue),size_list_queue(queue));
110 }
111 printf("-------------\n");
112 while(!empty_list_queue(queue))
113 {
114 printf("head:%d,size:%u\n",
115 head_list_queue(queue),size_list_queue(queue));
116 pop_list_queue(queue);
117 }
118 destroy_list_queue(queue);
119 queue = NULL;
120 }
121
122
队列的应用：
1、数据排队处理-消息排队
2、树的层序遍历
3、图的广度优先遍历BFS
4、封装线程池、数据池
标签：存储,return,队列,ArrayQueue,cnt,queue,cal,数据结构,rear From： https://www.cnblogs.com/wangqiuji/p/17587470.html