隊(duì)列

隊(duì)列的定義

隊(duì)列簡稱隊(duì)，是一種受限制的線性表，僅允許在表的一端插入，在表的另一端進(jìn)行刪除。

• 進(jìn)行插入的一端叫做隊(duì)頭
• 進(jìn)行刪除的一端叫做隊(duì)尾

隊(duì)的特點(diǎn)

• 先進(jìn)先出(FIFO)

順序隊(duì)（循環(huán)隊(duì)列）

順序隊(duì)主要以循環(huán)隊(duì)列的形式出現(xiàn)

循環(huán)隊(duì)列的要素

• 隊(duì)空狀態(tài) qu.rear == qu.front
• 隊(duì)滿狀態(tài) (qu.rear+1)%MAXSIZE == qu.front

結(jié)構(gòu)體定義

#define MAXSIZE 1024typedef struct _Queue {int data[MAXSIZE]; //數(shù)據(jù)int front; //隊(duì)首指針int rear; //隊(duì)尾指針 }SqQueue;

操作

采用 p = (p+1)%MAXSIZE;而不是p++的方式移動指針是為了能保證循環(huán)再利用性，使其在超過MAXSIZE后能重新回到原始位置

否則一個(gè)隊(duì)只存滿再全部取出后就不能再利用了

初始化

//初始化循環(huán)隊(duì)列 void initQueue(SqQueue &qu) {qu.front = qu.rear = 0; }

判斷隊(duì)空

//判斷隊(duì)空 //隊(duì)空返回真，否則返回假 bool isQueueEmpty(SqQueue qu) {if(qu.front == qu.rear) return true;else return false; }

判斷隊(duì)滿

//判斷隊(duì)滿 //隊(duì)滿返回真，否則假 bool isQueueFull(SqQueue qu) {if((qu.rear + 1) % MAXSIZE == qu.front)return true;elsereturn false; }

進(jìn)隊(duì)

//進(jìn)隊(duì) bool enQueue(SqQueue &qu, int e) {//判斷隊(duì)滿if(isQueueFull(qu)) return false;//若未滿，先移動尾指針再存元素qu.rear = (qu.rear + 1) % MAXSIZE;qu.data[qu.rear] = e;return true; }

出隊(duì)

//出隊(duì) bool deQueue(SqQueue &qu, int &e) {//判斷隊(duì)空if(isQueueEmpty(qu)) return false;//若不為空，則先移動頭指針(因?yàn)榈扔?的時(shí)候并無元素，所以可以先移動指針)qu.front = (qu.front + 1) % MAXSIZE;e = qu.data[qu.front];return true; }

鏈隊(duì)

鏈隊(duì)的要素

• 隊(duì)空狀態(tài) lqu->rear == NULL 或 lqu->front == NULL
• 隊(duì)滿狀態(tài)不存在（假設(shè)內(nèi)存無限大）

結(jié)構(gòu)體定義

//儲存數(shù)據(jù)的鏈隊(duì)結(jié)點(diǎn) typedef struct QNode {int data; //數(shù)據(jù)域struct QNode *next; //指針域 }QNode;//頭結(jié)點(diǎn)定義，用于指示隊(duì)頭和隊(duì)尾 typedef struct _LiQueue {QNode *front;QNode *rear; }LiQueue;

操作

初始化

//初始化 bool initQueue(LiQueue* &lqu) {lqu = new LiQueue;if(!lqu) return false;lqu->front = lqu->rear = NULL;return true; }

判斷隊(duì)空

//判斷隊(duì)空，隊(duì)空返回真，否則假 bool isQueueEmpty(LiQueue *lqu) {if(!lqu->rear || !lqu->front)return true;elsereturn false; }

進(jìn)隊(duì)

//入隊(duì) bool enQueue(LiQueue* &lqu, int e) {QNode *node = new QNode;if(!node) return false;node->data = e;node->next = NULL;//若隊(duì)為空，則新結(jié)點(diǎn)即時(shí)隊(duì)首結(jié)點(diǎn)又是隊(duì)尾結(jié)點(diǎn)if(!lqu->rear)lqu->rear = lqu->front = node;else{lqu->rear->next = node;lqu->rear = node;}return true; }

出隊(duì)

//出隊(duì) bool deQueue(LiQueue* &lqu, int &e) {QNode *p;//判斷隊(duì)空if(!lqu->rear) return false;else p = lqu->front;//當(dāng)隊(duì)中只有一個(gè)保存數(shù)據(jù)的結(jié)點(diǎn)時(shí)需特殊操作if(lqu->front == lqu->rear)lqu->rear = lqu->front = NULL;elselqu->front = lqu->front->next;e = p->data;delete p;return true; }

總結(jié)

以上是生活随笔為你收集整理的队列及其操作的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。