如何实现循环队列运行（如何实现循环队列操作）

生活中有很多队列的影子，比如打饭排队，买火车票排队问题等，可以说与时间相关的问题，一般都会涉及到队列问题；从生活中，可以抽象出队列的概念，队列就是一个能够实现“先进先出”的存储结构。队列分为链式队列和静态队列；静态队列一般用数组来实现，但此时的队列必须是循环队列，否则会造成巨大的内存浪费；链式队列是用链表来实现队列的。

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 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 #ifndef SQQUEUE_H_INCLUDED #define SQQUEUE_H_INCLUDED /* 防止重复包含 */ ////////////////////////////////////////// //包含头文件 #include <stdlib.h> #include "ds.h" // OK, Status 等定义 //数据元素的类型(缺省使用int型) #ifndef ElemType #define ElemType int #define USE_DEFAULT_ELEMTYPE /* 使用缺省类型的标志 */ #endif //ElemType ////////////////////////////////////////// //循环队列的存储结构 #define MAXQSIZE 500/* 循环队列的最大容量 */ typedef struct { /* TODO (#1#): 这里完成循环队列的类型定义 */ ElemType *base; int front; int rear; //.................................... } SqQueue; ////////////////////////////////////////// //循环队列的基本操作 //构造一个空队列Q Status InitQueue(SqQueue &Q) { /* TODO (#2#): 构造空队列 */ Q.base=(ElemType*)malloc(MAXQSIZE *sizeof(ElemType)); if(!Q.base)exit(OVERFLOW); QQ.front=Q.rear =0; return OK; //TODO: 替换这行代码,以下同 //.................................... } //销毁队列Q // 前提：队列Q已存在 Status DestroyQueue(SqQueue &Q) { /* TODO (#3#): 销毁队列 */ free(Q.base); Q.base=NULL; Q.front=0; Q.rear=0; return OK; //.................................... } //将队列Q清为空队列 // 前提：队列Q已存在 Status ClearQueue(SqQueue &Q) { /* TODO (#4#): 清空队列 */ Q.base=0; Q.rear=0; return OK; //.................................... } //若队列Q为空，则返回TRUE，否则FALSE // 前提：队列Q已存在 Status QueueEmpty(SqQueue Q) { /* TODO (#5#): 判断队列是否为空 */ if(Q.front==Q.rear) return OK; else return ERROR; //.................................... } //返回队列Q的元素个数，即队列长度 // 前提：队列Q已存在 int QueueLength(SqQueue Q) { /* TODO (#6#): 返回队列长度 */ return (Q.rear-Q.front+MAXQSIZE)%MAXQSIZE; //.................................... } //取队列Q头元素用e返回 // 前提：队列Q存在且非空 Status GetHead(SqQueue Q,ElemType &e) { /* TODO (#7#): 取队头元素存入e */ if(Q.rear==Q.front) return ERROR; e=Q.base[Q.front]; //e=*(Q.base+Q.front); return OK;//返回操作状态(成功:OK,失败:ERROR) //.................................... } //插入元素e作为队列Q的新的队尾元素 // 前提：队列Q存在且未满 Status EnQueue(SqQueue &Q, ElemType e) { /* TODO (#8#): 元素e入队列 */ if((Q.rear+1)%MAXQSIZE==Q.front) return ERROR; //e=*(Q.base +Q.rear); Q.base[Q.rear]=e; Q.rear=(Q.rear+1)%MAXQSIZE; return OK;//返回操作状态(成功:OK,失败:ERROR) //.................................... } //删除队列Q的队头元素，并用e返回 // 前提：队列Q存在且非空 Status DeQueue(SqQueue &Q, ElemType e) { /* TODO (#9#): 出队列存入e */ if(Q.front==Q.rear) return ERROR; //e=*(Q.base+Q.front); e=Q.base[Q.front]; Q.front=(Q.front+1)%MAXQSIZE; return OK;//返回操作状态(成功:OK,失败:ERROR) //.................................... } ////////////////////////////////////////// //TODO: 定义好 SqQueue 类型后使用 QueueView 函数 /****** //TODO: 删除此行以便使用QueueView() #include <stdio.h> //查看队列状态(调试用) void QueueView(SqQueue Q) { extern void PrintElem(ElemType e);//打印数据用 int i=0; if(Q.front<0||Q.front>=MAXQSIZE||Q.rear<0||Q.rear>=MAXQSIZE){ printf("队列未初始化\n"); return ; } printf("---Queue View---\n"); printf("front=%d , rear=%d\n", Q.front, Q.rear); if(Q.rear>=Q.front) { printf("..... ......\n"); for(i=Q.front; i<Q.rear; i++) { printf("%5d\t", i); PrintElem(Q.base[i]); printf("\n"); } if(i<MAXQSIZE) printf("..... ......\n"); } else { for(i=0; i<Q.rear; i++) { printf("%5d\t", i); PrintElem(Q.base[i]); printf("\n"); } printf("..... ......\n"); for(i=Q.front; i<MAXQSIZE; i++) { printf("%5d\t", i); PrintElem(Q.base[i]); printf("\n"); } } printf("--- view end ---\n"); } ******/ //TODO: 删除此行以便使用QueueView() //取消ElemType的默认定义，以免影响其它部分 #ifdef USE_DEFAULT_ELEMTYPE #undef ElemType #undef USE_EFAULT_ELEMTYPE #endif #endif //SQQUEUE_H_INCLUDED #include <stdio.h> #include <stdlib.h> #include "sqqueue.h" //初始化系统 void Finalize(SqQueue &q); //////////////////////////////////////////// //主程序 int main() { SqQueue q; //循环队列 int x; //系统初始化 InitQueue(q); printf("数据元素进队列,以0结束"); scanf("%d",&x); while(x!=0){ EnQueue(q,x); scanf("%d",&x); } printf("\n队列元素的个数"); printf("%d",QueueLength(q)); printf("\n头元素是："); if(!QueueEmpty(q)){ if(GetHead(q,x)==OK) printf("%d",x); } printf("\n出队列,先进先出"); if( DeQueue(q,x)==OK) printf("%d",x); printf("\n此时的对头是："); if(!QueueEmpty(q)){ if(GetHead(q,x)==OK) printf("%d\n",x); } }