1.队列的定义
队列 (Queue)是另一种限定性的线性表,它只允许在表的一端插入元素,而在另一端删除元素,所以队列具有先进先出(Fist In Fist Out,缩写为FIFO)的特性。在队列中,允许插入的一端叫做队尾(rear),允许删除的一端则称为队头(front)。 假设队列为q=(a1,a2,…,an),那么a1就是队头元素,an则是队尾元素。队列中的元素是按照a1、a2、…、an的顺序进入的, 退出队列也必须按照同样的次序依次出队,也就是说,只有在a1、a2、…、an-1都离开队列之后,an才能退出队列。
2.队列的表示和实现
链队列可以定义如下:
1
2
3
4
5
6
7
8
9
10
|
#define TRUE 1 #define FALSE 0 typedef struct QNode{ QElemType data; struct QNode *next; }QNode, *QueuePtr; typedef struct { QueuePtr front; QueuePtr rear; }LinkQueue; |
(1) 初始化操作
1
2
3
4
5
6
7
|
Status InitQueue(LinkQueue &Q) { Q.front = Q.rear = (Queueptr) malloc ( sizeof (QNode)); if (!Q.front) exit ( OVERFLOW); Q.front ->next = NULL; return OK; } |
(2)销毁队列
1
2
3
4
5
6
7
8
9
|
Status DestroyQueue(LinkQueue &Q) { while (Q.front) { Q.rear = Q.front->next; free (Q.front); Q.front = Q.rear; } return OK; } |
(3) 入队操作
1
2
3
4
5
6
7
8
9
|
Status EnQueue (LinkQueue &Q, QelemType e) { p= (QueuePtr) malloc ( sizeof (QNode)); if (!p) exit ( OVERFLOW); p->data = e; p->next = NULL; Q.rear -> next =p; Q.rear = p; return OK; } |
(4) 出队操作
1
2
3
4
5
6
7
8
9
10
|
Status DeQueue (LinkQueue &Q, QelemType &e) { if ( Q.front == Q.rear) return ERROR; p=Q.front->next; e=p->data; Q.front->next =p->next; if (Q.rear == p) Q.rear = Q.front; free (p); return OK; } |
附录完整代码:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
|
#include<iostream> using namespace std; #define OK 1 #define FALSE 0 typedef int QElemType; typedef int Status; typedef struct QNode{ QElemType data; struct QNode *next; }QNode,*QueuePtr; typedef struct { QueuePtr font; QueuePtr near; }LinkQueue; Status InitQueue(LinkQueue &Q) { Q.font=(QueuePtr) malloc ( sizeof (QNode)); if (!Q.font) exit (FALSE); Q.font->next=NULL; Q.near=Q.font; return OK; } Status QueueEmpty(LinkQueue Q) { if (Q.font->next) return OK; return FALSE; } Status EnQueue(LinkQueue &Q,QElemType e) { QueuePtr p=(QueuePtr) malloc ( sizeof (QNode)); p->data=e; Q.near->next = p; Q.near = Q.near->next; p->next = NULL; return OK; } Status DeQueue(LinkQueue &Q,QElemType &e) { if (!Q.font->next) return FALSE; QueuePtr p; p=Q.font->next; e=p->data; Q.font->next=p->next; if (Q.near==p) Q.near=Q.font; //当是最后一个元素时,Q.font=NULL,Q.near=Q.font free (p); return OK; } Status ClearQueue(LinkQueue &Q) { QueuePtr p; p=Q.font->next; QueuePtr q; while (p) { q=p; p=p->next; Q.font->next=p; free (q); } Q.near=Q.font; return OK; } void menu() { cout<< "初始化队列:1" <<endl; cout<< "入队:2" <<endl; cout<< "出队:3" <<endl; cout<< "清空队列:4" <<endl; cout<< "退出:5" <<endl; } int main() { LinkQueue Q; while ( true ) { int n; menu(); scanf ( "%d" ,&n); int e=-1; switch (n) { case 1: InitQueue(Q); continue ; case 2: printf ( "请输入一个元素" ); scanf ( "%d" ,&e); EnQueue(Q,e); continue ; case 3: DeQueue(Q,e); printf ( "\n出队元素%d\n" ,e); continue ; case 4: ClearQueue(Q); printf ( "清空成功\n" ); continue ; default : break ; } if (n==5) break ; } } |
总结
本篇文章就到这里了,希望能够给你带来帮助,也希望您能够多多关注服务器之家的更多内容!
原文链接:https://blog.csdn.net/m0_52118763/article/details/122203877