2.3. 队列
具有一定操作约束的线性表。 只在一端(队尾)做插入,在另一端(队头)删除操作。
抽象数据结构描述
Queue CreateQueue(): 生成一个容量为maxsize 的空队列。
int IsFullQ(Queue q,int maxsize): 判断队列是否满了。
void AddQ(Queue q,ElementType item): 将元素item插入队列。
int IsEmptyQ(Queue q): 判断队列是否为空。
ElementType DeleteQ(Queue q): 将队头数据从队列删除并返回。
2.3.1. 队列的顺序存储具体实现
1#include <stdio.h>
2#include <stdlib.h>
3
4#define ElementType int
5#define ERROR -9999
6#define MAXSIZE 5
7typedef struct QNode *Queue;
8struct QNode {
9 ElementType Data[MAXSIZE];
10 int real;
11 int front;
12};
13
14int IsFullQ(Queue q) {
15 if ((q->real + 1) % MAXSIZE == q->front) {
16 return 1;
17 }
18 return 0;
19}
20
21int IsEmptyQ(Queue q) {
22 if (q->real == q->front) {
23 return 1;
24 }
25 return 0;
26}
27
28Queue CreateQueue() {
29 Queue q = (Queue) malloc(sizeof(struct QNode));
30 q->front = 0;
31 q->real = 0;
32 return q;
33}
34
35void AddQ(Queue q, ElementType item) {
36 if (IsFullQ(q) == 1) {
37 printf("full \n");
38 return;
39 }
40 q->real = (q->real + 1) % MAXSIZE;
41 q->Data[q->real] = item;
42}
43
44ElementType DeleteQ(Queue q) {
45 if (IsEmptyQ(q) == 1) {
46 printf("empty \n");
47 return ERROR;
48 }
49 q->front = (q->front + 1) % MAXSIZE;
50 return q->Data[q->front];
51}
52
53int main() {
54 Queue q = CreateQueue();
55 ElementType item;
56 printf("is empty ? %d\n", IsEmptyQ(q));
57 AddQ(q, 1);
58 AddQ(q, 2);
59 AddQ(q, 3);
60 AddQ(q, 4);
61 AddQ(q, 5);
62 AddQ(q, 6);
63 AddQ(q, 7);
64 item = DeleteQ(q);
65 printf("item= %d\n", item);
66 item = DeleteQ(q);
67 printf("item= %d\n", item);
68 item = DeleteQ(q);
69 printf("item= %d\n", item);
70 item = DeleteQ(q);
71 printf("item= %d\n", item);
72
73 /*
74is empty ? 1
75full
76full
77full
78item= 1
79item= 2
80item= 3
81item= 4
82 * */
83}
2.3.2. 队列的顺序存储具体实现
1#include <stdio.h>
2#include <stdlib.h>
3
4#define ElementType int
5#define ERROR -9999
6struct Node {
7 ElementType Data;
8 struct Node *Next ;
9};
10
11typedef struct QNode *Queue ;
12struct QNode {
13 struct Node *real;
14 struct Node *front;
15};
16
17
18int IsFullQ(Queue q) {
19 return 0 ;
20}
21
22int IsEmptyQ(Queue q) {
23 if ( q->front == NULL){
24 return 1 ;
25 }
26 return 0 ;
27}
28
29Queue CreateQueue() {
30 Queue q = (Queue)malloc(sizeof(struct QNode)) ;
31 q->front = NULL ;
32 q->real = NULL ;
33 return q ;
34}
35
36void AddQ(Queue q, ElementType item) {
37 struct Node *node = (struct Node *)malloc(sizeof(struct Node)) ;
38 node->Next = NULL;
39 node->Data = item ;
40 if (q->real ==NULL){
41 q->real = node ;
42 }else{
43 q->real->Next = node;
44 q->real = q->real->Next ;
45 }
46 if (q->front == NULL){
47 q->front = node ;
48 }
49
50}
51
52ElementType DeleteQ(Queue q) {
53 if (IsEmptyQ(q) == 1) {
54 printf("empty \n");
55 return ERROR;
56 }
57 ElementType firstValue ;
58 struct Node *frontNode ;
59
60 frontNode= q->front ;
61 if (q->front == q->real ){
62 q->front = NULL;
63 q->real = NULL;
64
65 }else{
66 q->front = q->front->Next ;
67 }
68 firstValue = frontNode->Data;
69 free(frontNode);
70 return firstValue ;
71
72}
73
74
75
76int main() {
77 Queue q = CreateQueue();
78 ElementType item;
79 printf("is empty ? %d\n", IsEmptyQ(q));
80 AddQ(q, 1);
81 AddQ(q, 2);
82 AddQ(q, 3);
83 AddQ(q, 4);
84
85 item = DeleteQ(q);
86 printf("item= %d\n", item);
87 item = DeleteQ(q);
88 printf("item= %d\n", item);
89 item = DeleteQ(q);
90 printf("item= %d\n", item);
91 item = DeleteQ(q);
92 printf("item= %d\n", item);
93 item = DeleteQ(q);
94 printf("item= %d\n", item);
95 item = DeleteQ(q);
96 printf("item= %d\n", item);
97
98
99 return 0;
100 /*
101
102
103 */
104}