佇列

佇列，又稱為-{zh-hans:佇列;zh-hant:佇列}-進行刪除操作。佇列的操作方式和堆疊類似，唯一的區別在於佇列只允許新資料在後端進行新增。單鏈佇列.單鏈佇列使用連結串列作為基本資料結構，所以不存在偽溢位的問題，佇列長度也沒有限制。但插入和讀取的時間代價較高儲存結構./* c3-2.h 單鏈佇列－－佇列的鏈式儲存結構 */typedef struct QNodeQElemType data;struct QNode *next;}QNode,*QueuePtr;typedef structQueuePtr front,rear; /* 隊頭、隊尾指標 */}LinkQueue;基本操作./* bo3-2.c 鏈佇列(儲存結構由c3-2.h定義)的基本操作(9個) */void InitQueue(LinkQueue *Q)(*Q).front=(*Q).rear=(QueuePtr)malloc(sizeof(QNode));if(!(*Q).front)exit(OVERFLOW);(*Q).front-&gt;next=NULL;void DestroyQueue(LinkQueue *Q)while((*Q).front)(*Q).rear=(*Q).front-&gt;next;free((*Q).front);(*Q).front=(*Q).rear;void ClearQueue(LinkQueue *Q)QueuePtr p,q;(*Q).rear=(*Q).front;p=(*Q).front-&gt;next;(*Q).front-&gt;next=NULL;while(p)q=p;p=p-&gt;next;free(q);Status QueueEmpty(LinkQueue Q)if(Q.front-&gt;next==NULL)return TRUE;elsereturn FALSE;int QueueLength(LinkQueue Q)int i=0;QueuePtr p;p=Q.front;while(Q.rear!=p)i++;p=p-&gt;next;return i;Status GetHead_Q(LinkQueue Q,QElemType *e) /* 避免與bo2-6.c重名 */QueuePtr p;if(Q.front==Q.rear)return ERROR;p=Q.front-&gt;next;*e=p-&gt;data;return OK;void EnQueue(LinkQueue *Q,QElemType e)QueuePtr p=(QueuePtr)malloc(sizeof(QNode));if(!p) /* 儲存分配失敗 */exit(OVERFLOW);p-&gt;data=e;p-&gt;next=NULL;(*Q).rear-&gt;next=p;(*Q).rear=p;Status DeQueue(LinkQueue *Q,QElemType *e)QueuePtr p;if((*Q).front==(*Q).rear)return ERROR;p=(*Q).front-&gt;next;*e=p-&gt;data;(*Q).front-&gt;next=p-&gt;next;if((*Q).rear==p)(*Q).rear=(*Q).front;free(p);return OK;void QueueTraverse(LinkQueue Q,void(*vi)(QElemType))QueuePtr p;p=Q.front-&gt;next;while(p)vi(p-&gt;data);p=p-&gt;next;printf("\n");迴圈佇列.迴圈佇列可以更簡單防止偽溢位的發生，但佇列大小是固定的。// 佇列的順序儲存結構(迴圈佇列)typedef struct {int *base; // 初始化的動態分配儲存空間int front; // 頭指標，若佇列不空，指向佇列頭元素int rear; // 尾指標，若佇列不空，指向佇列尾元素的下一個位置} SqQueue;// 構造一個空佇列QSqQueue* Q_Init() {SqQueue *Q = (SqQueue*)malloc(sizeof(SqQueue));// 儲存分配失敗if (!Q){exit(OVERFLOW);Q-&gt;base = (int *)malloc(MAX_QSIZE * sizeof(int));// 儲存分配失敗if (!Q-&gt;base){exit(OVERFLOW);Q-&gt;front = Q-&gt;rear = 0;return Q;// 銷燬佇列Q，Q不再存在void Q_Destroy(SqQueue *Q) {if (Q-&gt;base)free(Q-&gt;base);Q-&gt;base = NULL;Q-&gt;front = Q-&gt;rear = 0;free(Q);// 將Q清為空佇列void Q_Clear(SqQueue *Q) {Q-&gt;front = Q-&gt;rear = 0;// 若佇列Q為空佇列，則返回1；否則返回-1int Q_Empty(SqQueue Q) {if (Q.front == Q.rear) // 佇列空的標誌return 1;elsereturn -1;// 返回Q的元素個數，即佇列的長度int Q_Length(SqQueue Q) {return (Q.rear - Q.front + MAX_QSIZE) % MAX_QSIZE;// 若佇列不空，則用e返回Q的隊頭元素，並返回OK；否則返回ERRORint Q_GetHead(SqQueue Q, int &amp;e) {if (Q.front == Q.rear) // 佇列空return -1;e = Q.base[Q.front];return 1;// 列印佇列中的內容void Q_Print(SqQueue Q) {int p = Q.front;while (Q.rear != p) {cout « Q.base[p] « endl;p = (p + 1) % MAX_QSIZE;// 插入元素e為Q的新的隊尾元素int Q_Put(SqQueue *Q, int e) {if ((Q-&gt;rear + 1) % MAX_QSIZE == Q-&gt;front) // 佇列滿return -1;Q-&gt;base[Q-&gt;rear] = e;Q-&gt;rear = (Q-&gt;rear + 1) % MAX_QSIZE;return 1;// 若佇列不空，則刪除Q的隊頭元素，用e返回其值，並返回1；否則返回-1int Q_Poll(SqQueue *Q, int &amp;e) {if (Q-&gt;front == Q-&gt;rear) // 佇列空return -1;e = Q-&gt;base[Q-&gt;front];Q-&gt;front = (Q-&gt;front + 1) % MAX_QSIZE;return 1;陣列佇列.// 陣列佇列的儲存結構struct Queue {int Array[MAX_QSIZE]; // 陣列空間大小int front; // 隊頭int rear; // 隊尾int length; // 佇列長度// 構造一個空佇列QQueue* Q_Init() {Queue *Q = (Queue*)malloc(sizeof(Queue));if (!Q){// 儲存分配失敗exit(OVERFLOW);//初始化Q-&gt;front = Q-&gt;rear = Q-&gt;length = 0;return Q;// 將Q清為空佇列void Q_Clear(Queue *Q) {//清除頭尾下標和長度Q-&gt;front = Q-&gt;rear = Q-&gt;length = 0;// 入列int Q_Put(Queue *Q, int x) {//如果當前元素數量等於最大數量 返回 -1if (Q-&gt;rear + 1 == MAX_QSIZE) {return -1;Q-&gt;Array[Q-&gt;rear] = x;Q-&gt;rear = Q-&gt;rear + 1;//length + 1Q-&gt;length = Q-&gt;length + 1;return 1;// 出列int Q_Poll(Queue *Q) {//如果當前元素數量等於最大數量 返回 -1if (Q-&gt;front + 1 == MAX_QSIZE)return -1;int x = Q-&gt;Array[Q-&gt;front];Q-&gt;front = Q-&gt;front + 1;// 移出後減少1Q-&gt;length = Q-&gt;length - 1;return x;