本页使用了标题或全文手工转换

队列

维基百科,自由的百科全书
跳转至: 导航搜索
Confusion grey.svg
提示:本条目的主题不是排队

队列,又称为伫列(queue),是先进先出(FIFO, First-In-First-Out)的线性表。在具体应用中通常用链表或者数组来实现。队列只允许在后端(称为rear)进行插入操作,在前端(称为front)进行删除操作。

队列的操作方式和堆栈类似,唯一的区别在于队列只允许新数据在后端进行添加。

单链队列[编辑]

单链队列使用链表作为基本数据结果,所以不存在伪溢出的问题,队列长度也没有限制。但插入和读取的时间代价较高

  1 // 单链队列——队列的链式存储结构
  2 typedef struct QNode {
  3     QElemType data;
  4     struct QNode *next;
  5 } QNode, *QueuePtr;
  6 
  7 typedef struct {
  8     QueuePtr front, rear; // 队头、队尾指针
  9 } LinkQueue;
 10 
 11 // 链队列的基本操作(9个)
 12 void InitQueue(LinkQueue *Q) {
 13     // 构造一个空队列Q
 14     Q->front = Q->rear = malloc(sizeof(QNode));
 15     if (!Q->front)
 16         exit(OVERFLOW);
 17     Q->front->next = NULL;
 18 }
 19 
 20 void DestroyQueue(LinkQueue *Q) {
 21     // 销毁队列Q(无论空否均可)
 22     while (Q->front) {
 23         Q->rear = Q->front->next;
 24         free(Q->front);
 25         Q->front = Q->rear;
 26     }
 27 }
 28 
 29 void ClearQueue(LinkQueue *Q) {
 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 
 42 Status QueueEmpty(LinkQueue Q) {
 43     // 若Q为空队列,则返回TRUE,否则返回FALSE
 44     if (Q.front->next == NULL)
 45         return TRUE;
 46     else
 47         return FALSE;
 48 }
 49 
 50 int QueueLength(LinkQueue Q) {
 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 
 62 Status GetHead_Q(LinkQueue Q, QElemType *e) {
 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]; // 陣列空間大小
 6     int head; // 前端(front)
 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) {
23     int x = Queue1->Array[Queue1->head];
24     if (Queue1->head + 1 == 10) // 空間大小10
25         Queue1->head = 0;
26     else
27         Queue1->head = Queue1->head + 1;
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 }

参见[编辑]