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

队列

维基百科,自由的百科全书
跳到导航 跳到搜索

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

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

单链队列[编辑]

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

  1 // 定义单链队列的存储结构
  2 typedef struct QNode {
  3     int data;
  4     QNode *next;
  5 }QNode,*QNodePtr;
  6 
  7 typedef struct LinkQueue{
  8     //队头 队尾 指针
  9     QNodePtr front,rear;
 10 }LinkQueue;
 11 
 12 
 13 // 构造一个空队列Q
 14 LinkQueue* Q_Init() {
 15     //申请内存
 16     LinkQueue* Q = (LinkQueue*)malloc(sizeof(LinkQueue));
 17     //如果 Q 为 NULL 说明 内存申请失败,结束程序
 18     if (!Q)
 19         exit(OVERFLOW);
 20     //初始化头尾节点 指向相同地址
 21     Q->front = Q->rear = (QNodePtr)malloc(sizeof(QNode));
 22     //如果 Q->front 为 NULL 说明 内存申请失败,结束程序
 23     if (!Q->front)
 24         exit(OVERFLOW);
 25     Q->front->next = NULL;
 26     return Q;
 27 }
 28 
 29 // 销毁队列Q(无论空否均可)
 30 void Q_Destroy(LinkQueue *Q) {
 31     while (Q->front) {
 32         //将队尾指向队头下一个节点的地址(第1个节点)
 33         Q->rear = Q->front->next;
 34         //回收队头
 35         free(Q->front);
 36         //将队头指向队尾(相当于第1个节点变成了队头,然后依次第2个第3个、、、
 37         //直到没有下一个节点,也就是 Q->front == NULL 的时候)
 38         Q->front = Q->rear;
 39     }
 40     free(Q);
 41 }
 42 
 43 // 将Q清为空队列
 44 void Q_Clear(LinkQueue *Q) {
 45     QNodePtr p, q;
 46     //将队尾指向队头点的地址
 47     Q->rear = Q->front;
 48     //取出第1个节点
 49     p = Q->front->next;
 50     //回收第1个节点
 51     Q->front->next = NULL;
 52     while (p) {
 53         //将 q 指向 p(第1个节点)
 54         q = p;
 55         //将 p 指向 第2个节点
 56         p = p->next;
 57         //回收第2个节点
 58         free(q);
 59     }
 60 }
 61 
 62 // 若Q为空队列,则返回-1,否则返回1
 63 int Q_Empty(LinkQueue Q) {
 64     if (Q.front->next == NULL)
 65         return 1;
 66     else
 67         return -1;
 68 }
 69 
 70 // 求队列的长度
 71 int Q_Length(LinkQueue Q) {
 72     int i = 0;
 73     QNodePtr p;
 74     p = Q.front;
 75     //遍历队列中的节点,直到队尾等于队头
 76     while (Q.rear != p) {
 77         i++;
 78         p = p->next;
 79     }
 80     return i;
 81 }
 82 
 83 // 打印队列中的内容
 84 void Q_Print(LinkQueue Q) {
 85     int i = 0;
 86     QNodePtr p;
 87     p = Q.front;
 88     while (Q.rear != p) {
 89         i++;
 90         cout << p->next->data << endl;
 91         p = p->next;
 92     }
 93 }
 94 
 95 // 若队列不空,则用e返回Q的队头元素,并返回1,否则返回-1
 96 int Q_GetHead(LinkQueue Q, int &e) {
 97     QNodePtr p;
 98     if (Q.front == Q.rear)
 99         return -1;
100     p = Q.front->next;
101     e = p->data;
102     return 1;
103 }
104 
105 // 插入元素e为Q的新的队尾元素
106 void Q_Put(LinkQueue *Q, int e) {
107     QNodePtr p = (QNodePtr)malloc(sizeof(QNode));
108     if (!p) // 存储分配失败
109         exit(OVERFLOW);
110     p->data = e;
111     p->next = NULL;
112     //FIFO,将新节点追加到尾节点后面
113     Q->rear->next = p;
114     //将新的节点变成尾节点
115     Q->rear = p;
116 }
117 
118 
119 // 若队列不空,删除Q的队头元素,用e返回其值,并返回1,否则返回-1
120 int Q_Poll(LinkQueue *Q,int &e) {
121     QNodePtr p;
122     if (Q->front == Q->rear)
123         return -1;
124     //取出头节点
125     p = Q->front->next;
126     //取出头节点的数据
127     e = p->data;
128     cout << e << endl;
129     Q->front->next = p->next;
130     if (Q->rear == p)
131         Q->rear = Q->front;
132     free(p);
133     cout << e << endl;
134     return 1;
135 }

循环队列[编辑]

循环队列可以更简单防止伪溢出的发生,但队列大小是固定的。

 1 // 队列的顺序存储结构(循环队列)
 2 #define MAX_QSIZE 5 // 最大队列长度+1
 3 typedef struct {
 4     int *base; // 初始化的动态分配存储空间
 5     int front; // 头指针,若队列不空,指向队列头元素
 6     int rear; // 尾指针,若队列不空,指向队列尾元素的下一个位置
 7 } SqQueue;
 8 
 9 
10 // 构造一个空队列Q
11 SqQueue* Q_Init() {
12     SqQueue *Q = (SqQueue*)malloc(sizeof(SqQueue));
13     // 存储分配失败
14     if (!Q){
15         exit(OVERFLOW);
16     }
17     Q->base = (int *)malloc(MAX_QSIZE * sizeof(int));
18     // 存储分配失败
19     if (!Q->base){
20         exit(OVERFLOW);
21     }
22     Q->front = Q->rear = 0;
23     return Q;
24 }
25 
26 // 销毁队列Q,Q不再存在
27 void Q_Destroy(SqQueue *Q) {
28     if (Q->base)
29         free(Q->base);
30     Q->base = NULL;
31     Q->front = Q->rear = 0;
32     free(Q);
33 }
34 
35 // 将Q清为空队列
36 void Q_Clear(SqQueue *Q) {
37     Q->front = Q->rear = 0;
38 }
39 
40 // 若队列Q为空队列,则返回1;否则返回-1
41 int Q_Empty(SqQueue Q) {
42     if (Q.front == Q.rear) // 队列空的标志
43         return 1;
44     else
45         return -1;
46 }
47 
48 // 返回Q的元素个数,即队列的长度
49 int Q_Length(SqQueue Q) {
50     return (Q.rear - Q.front + MAX_QSIZE) % MAX_QSIZE;
51 }
52 
53 // 若队列不空,则用e返回Q的队头元素,并返回OK;否则返回ERROR
54 int Q_GetHead(SqQueue Q, int &e) {
55     if (Q.front == Q.rear) // 队列空
56         return -1;
57     e = Q.base[Q.front];
58     return 1;
59 }
60 
61 // 打印队列中的内容
62 void Q_Print(SqQueue Q) {
63     int p = Q.front;
64     while (Q.rear != p) {
65         cout << Q.base[p] << endl;
66         p = (p + 1) % MAX_QSIZE;
67     }
68 }
69 
70 // 插入元素e为Q的新的队尾元素
71 int Q_Put(SqQueue *Q, int e) {
72     if ((Q->rear + 1) % MAX_QSIZE == Q->front) // 队列满
73         return -1;
74     Q->base[Q->rear] = e;
75     Q->rear = (Q->rear + 1) % MAX_QSIZE;
76     return 1;
77 }
78 
79 // 若队列不空,则删除Q的队头元素,用e返回其值,并返回1;否则返回-1
80 int Q_Poll(SqQueue *Q, int &e) {
81     if (Q->front == Q->rear) // 队列空
82         return -1;
83     e = Q->base[Q->front];
84     Q->front = (Q->front + 1) % MAX_QSIZE;
85     return 1;
86 }

陣列佇列[编辑]

 1 #define MAX_QSIZE 10 // 最大队列长度+1
 2 // 阵列队列的存储结构
 3 struct Queue {
 4     int Array[MAX_QSIZE]; // 阵列空间大小
 5     int front; // 队头
 6     int rear; // 队尾
 7     int length; // 队列长度
 8 };
 9 
10 // 构造一个空队列Q
11 Queue* Q_Init() {
12     Queue *Q = (Queue*)malloc(sizeof(Queue));
13     if (!Q){
14         // 存储分配失败
15         exit(OVERFLOW);
16     }
17     //初始化
18     Q->front = Q->rear = Q->length = 0;
19     return Q;
20 }
21 
22 // 将Q清为空队列
23 void Q_Clear(Queue *Q) {
24     //清除头尾下标和长度
25     Q->front = Q->rear = Q->length = 0;
26 }
27 
28 // 入列
29 int Q_Put(Queue *Q, int x) {
30     //如果当前元素数量等于最大数量 返回 -1
31     if (Q->rear + 1 == MAX_QSIZE) {
32         return -1;
33     }
34     Q->Array[Q->rear] = x;
35     Q->rear = Q->rear + 1;
36     //length + 1
37     Q->length = Q->length + 1;
38     return 1;
39 }
40 
41 // 出列
42 int Q_Poll(Queue *Q) {
43     //如果当前元素数量等于最大数量 返回 -1
44     if (Q->front + 1 == MAX_QSIZE)
45         return -1;
46     int x = Q->Array[Q->front];
47     Q->front = Q->front + 1;
48     // 移出后減少1
49     Q->length = Q->length - 1;
50     return x;
51 }

参见[编辑]