1 //循环队列的顺序存储表示与实现
2
3 #include <stdio.h>
4 #include <stdlib.h>
5
6 /******************************************************************************
7 /* 数据类型和常量定义
8 /******************************************************************************/
9 #define OK 1
10 #define ERROR 0
11 #define OVERFLOW -2
12
13 typedef int Status;
14 typedef int ElemType;
15 typedef int QElemType;
16
17 /******************************************************************************
18 /* 数据结构声明
19 /******************************************************************************/
20 /* 循环队列 - 队列的顺序存储结构 */
21 #define MAXQSIZE 3 /* 最大队列长度 */
22
23 typedef struct {
24 QElemType *base; /* 初始化的动态分配存储空间 */
25 int front; /* 头指针,若队列不空,指向队列头元素 */
26 int rear; /* 尾指针,若队列不空,指向队列尾元素的下一个位置 */
27 }SqQueue;
28
29
30 //构造一个空队列Q
31 Status InitQueue(SqQueue &Q) {
32 Q.base = (ElemType *)malloc(MAXQSIZE * sizeof(ElemType));
33 if (!Q.base) exit(OVERFLOW);
34 Q.front = Q.rear = 0;
35 return OK;
36 }
37
38
39 //返回Q的元素个数, 即队列的长度
40 int QueueLength(SqQueue &Q) {
41 return (Q.rear - Q.front + MAXQSIZE) % MAXQSIZE;
42 }
43
44
45 //插入元素e为Q的新的队尾元素
46 Status EnQueue(SqQueue &Q, QElemType e) {
47 if ((Q.rear + 1) % MAXQSIZE == Q.front) return ERROR; //队列满
48 Q.base[Q.rear] = e;
49 Q.rear = (Q.rear + 1) % MAXQSIZE;
50 return OK;
51 }
52
53
54 //若队列不空, 则删除Q的队头元素, 用e返回其值, 并返回OK; 否则返回ERROR
55 Status DeQueue(SqQueue &Q, QElemType &e) {
56 if (Q.front == Q.rear) return ERROR;
57 e = Q.base[Q.front];
58 Q.front = (Q.front + 1) % MAXQSIZE;
59 return OK;
60 }
61
62 //测试函数
63 void main()
64 {
65 SqQueue Q; QElemType e;
66 InitQueue(Q);
67 if(OK == EnQueue(Q, 10)) printf("enqueue ok!\n");
68 if(OK == EnQueue(Q, 20)) printf("enqueue ok!\n");
69 if(OK == EnQueue(Q, 30)) printf("enqueue ok!\n");
70 if(OK == DeQueue(Q, e)) printf("%d\n", e);
71 if(OK == DeQueue(Q, e)) printf("%d\n", e);
72 if(OK == DeQueue(Q, e)) printf("%d\n", e);
73 if(OK == DeQueue(Q, e)) printf("%d\n", e);
74 }