如何實現循環隊列

2020-01-26 15:01:18

字體：大中小

來源：轉載

供稿：網友

生活中有很多隊列的影子，比如打飯排隊，買火車票排隊問題等，可以說與時間相關的問題，一般都會涉及到隊列問題；從生活中，可以抽象出隊列的概念，隊列就是一個能夠實現“先進先出”的存儲結構。隊列分為鏈式隊列和靜態隊列；靜態隊列一般用數組來實現，但此時的隊列必須是循環隊列，否則會造成巨大的內存浪費；鏈式隊列是用鏈表來實現隊列的。

#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);   }  }

實現的效果：