# 佇列

## 目錄

### 單鏈佇列

```  1 // 单链队列——队列的链式存储结构
2 typedef struct QNode {
3     QElemType data;
4     struct QNode *next;
5 } QNode, *QueuePtr;
6
7 typedef struct {
8     QueuePtr front, rear; // 队头、队尾指针
10
11 // 链队列的基本操作(9个)
13     // 构造一个空队列Q
14     Q->front = Q->rear = malloc(sizeof(QNode));
15     if (!Q->front)
16         exit(OVERFLOW);
17     Q->front->next = NULL;
18 }
19
21     // 销毁队列Q(无论空否均可)
22     while (Q->front) {
23         Q->rear = Q->front->next;
24         free(Q->front);
25         Q->front = Q->rear;
26     }
27 }
28
30     // 将Q清为空队列
31     QueuePtr p, q;
32     Q->rear = Q->front;
33     p = Q->front->next;
34     Q->front->next = NULL;
35     while (p) {
36         q = p;
37         p = p->next;
38         free(q);
39     }
40 }
41
43     // 若Q为空队列，则返回TRUE，否则返回FALSE
44     if (Q.front->next == NULL)
45         return TRUE;
46     else
47         return FALSE;
48 }
49
51     // 求队列的长度
52     int i = 0;
53     QueuePtr p;
54     p = Q.front;
55     while (Q.rear != p) {
56         i++;
57         p = p->next;
58     }
59     return i;
60 }
61
63     // 若队列不空，则用e返回Q的队头元素，并返回OK，否则返回ERROR
64     QueuePtr p;
65     if (Q.front == Q.rear)
66         return ERROR;
67     p = Q.front->next;
68     *e = p->data;
69     return OK;
70 }
71
72 void EnQueue(LinkQueue *Q, QElemType e) {
73     // 插入元素e为Q的新的队尾元素
74     QueuePtr p = (QueuePtr)malloc(sizeof(QNode));
75     if (!p) // 存储分配失败
76         exit(OVERFLOW);
77     p->data = e;
78     p->next = NULL;
79     Q->rear->next = p;
80     Q->rear = p;
81 }
82
83 Status DeQueue(LinkQueue *Q, QElemType *e) {
84     // 若队列不空，删除Q的队头元素，用e返回其值，并返回OK，否则返回ERROR
85     QueuePtr p;
86     if (Q->front == Q->rear)
87         return ERROR;
88     p = Q->front->next; // 指向头结点
89     *e = p->data;
90     Q->front = p->next; // 摘下头节点
91     if (Q->rear == p)
92         Q->rear = Q->front;
93     free(p);
94     return OK;
95 }
96
97 void QueueTraverse(LinkQueue Q, void(*vi)(QElemType)) {
98     // 从队头到队尾依次对队列Q中每个元素调用函数vi()
99     QueuePtr p;
100     p = Q.front->next;
101     while (p) {
102         vi(p->data);
103         p = p->next;
104     }
105     printf("\n");
106 }
```

### 循環佇列

``` 1 // 队列的顺序存储结构(循环队列)
2 #define MAX_QSIZE 5 // 最大队列长度+1
3 typedef struct {
4     QElemType *base; // 初始化的动态分配存储空间
5     int front; // 头指针，若队列不空，指向队列头元素
6     int rear; // 尾指针，若队列不空，指向队列尾元素的下一个位置
7 } SqQueue;
8
9 // 循环队列的基本操作(9个)
10 void InitQueue(SqQueue *Q) {
11     // 构造一个空队列Q
12     Q->base = malloc(MAX_QSIZE * sizeof(QElemType));
13     if (!Q->base) // 存储分配失败
14         exit(OVERFLOW);
15     Q->front = Q->rear = 0;
16 }
17
18 void DestroyQueue(SqQueue *Q) {
19     // 销毁队列Q，Q不再存在
20     if (Q->base)
21         free(Q->base);
22     Q->base = NULL;
23     Q->front = Q->rear = 0;
24 }
25
26 void ClearQueue(SqQueue *Q) {
27     // 将Q清为空队列
28     Q->front = Q->rear = 0;
29 }
30
31 Status QueueEmpty(SqQueue Q) {
32     // 若队列Q为空队列，则返回TRUE；否则返回FALSE
33     if (Q.front == Q.rear) // 队列空的标志
34         return TRUE;
35     else
36         return FALSE;
37 }
38
39 int QueueLength(SqQueue Q) {
40     // 返回Q的元素个数，即队列的长度
41     return (Q.rear - Q.front + MAX_QSIZE) % MAX_QSIZE;
42 }
43
44 Status GetHead(SqQueue Q, QElemType *e) {
45     // 若队列不空，则用e返回Q的队头元素，并返回OK；否则返回ERROR
46     if (Q.front == Q.rear) // 队列空
47         return ERROR;
48     *e = Q.base[Q.front];
49     return OK;
50 }
51
52 Status EnQueue(SqQueue *Q, QElemType e) {
53     // 插入元素e为Q的新的队尾元素
54     if ((Q->rear + 1) % MAX_QSIZE == Q->front) // 队列满
55         return ERROR;
56     Q->base[Q->rear] = e;
57     Q->rear = (Q->rear + 1) % MAX_QSIZE;
58     return OK;
59 }
60
61 Status DeQueue(SqQueue *Q, QElemType *e) {
62     // 若队列不空，则删除Q的队头元素，用e返回其值，并返回OK；否则返回ERROR
63     if (Q->front == Q->rear) // 队列空
64         return ERROR;
65     *e = Q->base[Q->front];
66     Q->front = (Q->front + 1) % MAX_QSIZE;
67     return OK;
68 }
69
70 void QueueTraverse(SqQueue Q, void(*vi)(QElemType)) {
71     // 从队头到队尾依次对队列Q中每个元素调用函数vi()
72     int i;
73     i = Q.front;
74     while (i != Q.rear) {
75         vi(Q.base[i]);
76         i = (i + 1) % MAX_QSIZE;
77     }
78     printf("\n");
79 }
```

## 陣列佇列

``` 1 #include <stdio.h>
2 #include <stdlib.h>
3 // 佇列資料結構
4 struct Queue {
5     int Array[10]; // 陣列空間大小
7     int tail; // 後端(rear)
8     int length; // 佇列長度，將其視為當前资料大小，並且使用這個成員判斷滿或空
9 };
10
11 // 資料加入佇列
12 void EnQueue(struct Queue *Queue1, int x) {
13     Queue1->Array[Queue1->tail] = x;
14     if (Queue1->tail + 1 == 10) { // Queue1->length改為空間大小10
15         Queue1->tail = 0; // 1改為0
16     } else
17         Queue1->tail = Queue1->tail + 1;
18     Queue1->length = Queue1->length + 1; // 當前個數增1
19 }
20
21 // 資料移出佇列
22 int DeQueue(struct Queue *Queue1) {
24     if (Queue1->head + 1 == 10) // 空間大小10
26     else
28     Queue1->length = Queue1->length - 1; // 移出后減少1
29     return x;
30 }
31
32 // 佇列操作
33 int main() {
34     struct Queue *Queue1 = malloc(sizeof(struct Queue)); // 建立資料結構
35     Queue1->length = 0; // 新增長度//10改為0，初始狀態
36     Queue1->head = 0; // 必須要先初始化
37     Queue1->tail = 0; // 必須要先初始化
38     EnQueue(Queue1, 5); // 將5放入佇列
39     EnQueue(Queue1, 8); // 將8放入佇列
40     EnQueue(Queue1, 3); // 將3放入佇列
41     EnQueue(Queue1, 2); // 將2放入佇列
42     printf("%d ", DeQueue(Queue1)); // 輸出佇列(5)
43     printf("%d ", DeQueue(Queue1)); // 輸出佇列(8)
44     printf("%d ", DeQueue(Queue1)); // 輸出佇列(3)
45     system("pause");
46 }
```