文章目錄

• • 1 隊列的鏈式存儲實現(xiàn)

1 隊列的鏈式存儲實現(xiàn)

隊列的鏈式存儲結(jié)構(gòu)，其實就是線性表的單鏈表，只不過它只是尾進頭出而已，我們把它簡稱為鏈隊列。為了操作上的方便，我們將隊頭指針指向鏈隊列的頭結(jié)點，而隊尾指針指向終端節(jié)點。

鏈式隊列操作圖示：
空隊列時，front 和 rear 都指向空。

刪除節(jié)點：

代碼實現(xiàn)如下：

#include <stdio.h> #include <assert.h> #include <Windows.h> #include <iostream> #include <iomanip>using namespace std;#define MaxSize 5 //隊列的最大容量typedef int DataType; //隊列中元素類型typedef struct _QNode { //結(jié)點結(jié)構(gòu)DataType data;struct _QNode* next; }QNode;typedef QNode* QueuePtr;typedef struct Queue {int length; //隊列的長度QueuePtr front; //隊頭指針QueuePtr rear; //隊尾指針 }LinkQueue;//隊列初始化，將隊列初始化為空隊列 void InitQueue(LinkQueue* LQ) {if (!LQ) return;LQ->length = 0;LQ->front = LQ->rear = NULL; //把對頭和隊尾指針同時置 0 }//判斷隊列為空 int IsEmpty(LinkQueue* LQ) {if (!LQ) return 0;if (LQ->front == NULL){return 1;}return 0; }//判斷隊列是否為滿 int IsFull(LinkQueue* LQ) {if (!LQ) return 0;if (LQ->length == MaxSize){return 1;}return 0; }//入隊,將元素 data 插入到隊列 LQ 中 int EnterQueue(LinkQueue* LQ, DataType data) {if (!LQ) return 0;if (IsFull(LQ)) {cout << "無法插入元素 " << data << ", 隊列已滿!" << endl;return 0;}QNode* qNode = new QNode;qNode->data = data;qNode->next = NULL;if (IsEmpty(LQ)) {//空隊列LQ->front = LQ->rear = qNode;}else {LQ->rear->next = qNode;//在隊尾插入節(jié)點 qNodeLQ->rear = qNode; //隊尾指向新插入的節(jié)點}LQ->length++;return 1; }//出隊，將隊列中隊頭的元素出隊，其后的第一個元素成為新的隊首 int DeleteQueue(LinkQueue* LQ, DataType* data) {QNode* tmp = NULL;if (!LQ || IsEmpty(LQ)) {cout << "隊列為空！" << endl;return 0;}if (!data) return 0;tmp = LQ->front;LQ->front = tmp->next;if (!LQ->front) LQ->rear = NULL;//如果對頭出列后不存在其他元素，則rear 節(jié)點也要置空* data = tmp->data;LQ->length--;delete tmp;return 1; }//打印隊列中的各元素 void PrintQueue(LinkQueue* LQ) {QueuePtr tmp;if (!LQ) return;if (LQ->front == NULL) {cout << "隊列為空！";return;}tmp = LQ->front;while (tmp){cout << setw(4) << tmp->data;tmp = tmp->next;}cout << endl; }//獲取隊首元素，不出隊 int GetHead(LinkQueue* LQ, DataType* data) {if (!LQ || IsEmpty(LQ)){cout << "隊列為空!" << endl;return 0;}if (!data) return 0;*data = LQ->front->data;return 1; }//清空隊列 void ClearQueue(LinkQueue* LQ) {if (!LQ) return;while (LQ->front) {QueuePtr tmp = LQ->front->next;delete LQ->front;LQ->front = tmp;}LQ->front = LQ->rear = NULL;LQ->length = 0; }//獲取隊列中元素的個數(shù) int getLength(LinkQueue* LQ) {if (!LQ) return 0;return LQ->length; }int main() {LinkQueue* LQ = new LinkQueue;DataType data = -1;//初始化隊列InitQueue(LQ);//入隊for (int i = 0; i < 7; i++) {EnterQueue(LQ, i);}//打印隊列中的元素printf("隊列中的元素(總共%d 個)：", getLength(LQ));PrintQueue(LQ);cout << endl;//出隊//for(int i=0; i<10; i++){if (DeleteQueue(LQ, &data)) {cout << "出隊的元素是：" << data << endl;}else {cout << "出隊失敗！" << endl;}//}//打印隊列中的元素printf("出隊一個元素后，隊列中剩下的元素[%d]：", getLength(LQ));PrintQueue(LQ);cout << endl;ClearQueue(LQ);cout << "清空隊列!\n";PrintQueue(LQ);//清理資源delete LQ;system("pause");return 0; }

---

參考資料：

C/C++從入門到精通-高級程序員之路【奇牛學(xué)院】

總結(jié)

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

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