文章目錄

• • • • 隊列：
      • 單鏈隊列的實現及操作：
      • • 1.定義一個隊列
        • 2.構造一個空隊列
        • 3.銷毀隊列
        • 4.插入元素e到隊尾
        • 5.刪除隊頭元素，用e返回其值
      • 單鏈隊列操作實例及代碼：

隊列：

隊列是先進先出的線性表。

隊列只允許在表的一端插入元素，在另一端刪除元素。

隊列中允許插入的一端叫隊尾，允許刪除的一端叫隊頭。

單鏈隊列的實現及操作：

1.定義一個隊列

一個鏈隊列，由每個結點連接起來。由于插入和刪除是在隊頭和隊尾進行的，我們為了方便起見，直接弄兩個指針，指向頭結點和隊尾元素所在結點。

typedef struct QNode {QElemType_L data;struct QNode *next; }QNode; typedef QNode* QueuePtr; typedef struct {QueuePtr front; QueuePtr rear; }LinkQueue;

2.構造一個空隊列

我們增加一個頭結點，首先分配一個頭結點的內存空間。當隊列為空時，隊頭指針和隊尾指針都指向頭結點，而且頭結點的指針域的指針指向空，意味著隊列里面沒有存元素。

Status InitQueue_L(LinkQueue &Q) {Q.front = Q.rear = (QueuePtr)malloc(sizeof(QNode));if(!Q.front)exit(OVERFLOW);Q.front->next = NULL;return OK; }

3.銷毀隊列

這個銷毀最終把頭結點也給銷毀了。

注意一點，鏈表知道頭指針，就能根據->next確定后面所有結點，我們初始化增加了一個尾指針，讓他指向最后一個結點，但這并不意味著我們改變了尾指針指向的位置，鏈表中間的結點就沒了，中間的結點還是可以根據頭指針和->next找到的，我們其實可以把尾指針理解成一個標記，他的位置并不影響鏈表，只不過方便了我們找隊尾元素所在結點。真正影響鏈表的是我們的頭指針，我們遍歷也是通過頭指針->next來的，每個結點都會用到。

這里我們就把尾指針當作一個轉移變量來用了。先存頭結點指向的下一個結點的位置，然后把頭結點的位置free掉，再讓頭結點指向尾指針指向的位置，即將下一個結點的位置當作頭結點。一路循環，當沒有下一個存元素的結點了，頭指針的位置指向頭結點，尾指針被賦為null，頭指針free之后頭結點的空間也沒了，然后把頭指針也賦為null。最終頭指針尾指針都指向null，而且所有空間全被free掉。

void DestroyQueue_L(LinkQueue &Q) {while(Q.front){Q.rear = Q.front->next;free(Q.front);Q.front = Q.rear; } }

如果是清空的話，有一點不同，就是還有頭結點，只不過->next指向null了，和初始狀態一樣，頭指針，尾指針指向頭結點，頭結點指向下一個結點的指針指向null。這里還是把尾指針當作一個轉移變量，初始指向第一個結點，每次讓頭指針指向的下一個結點變成尾指針這個轉移變量指向的下一個結點，然后free掉尾指針原來指向的結點，然后把當前尾指針指向的結點更新為尾指針這個轉移變量指向的下一個結點。舉個例子即可明白。

void ClearQueue_L(LinkQueue &Q) {Q.rear = Q.front->next;while(Q.rear){Q.front->next = Q.rear->next; free(Q.rear); Q.rear = Q.front->next;}Q.rear = Q.front; }

4.插入元素e到隊尾

插入元素，分配一個結點的空間，然后原尾指針的下一個位置指向新結點，更新尾指針。

Status EnQueue_L(LinkQueue &Q, QElemType_L e) {QueuePtr p;p = (QueuePtr)malloc(sizeof(QNode));if(!p)exit(OVERFLOW);p->data = e;p->next = NULL;Q.rear->next = p;Q.rear=p;return OK; }

5.刪除隊頭元素，用e返回其值

刪除先判端是否有元素，然后取出隊頭元素，讓頭結點指針域里面的指針指向的下一個結點變成第一個元素的結點指向的下一個元素的結點。

這里我們還要考慮是否對尾指針產生影響，當僅有一個元素時，刪除后隊列為空，尾指針應該指向頭結點。

最后把刪除的結點的空間釋放掉即可。

Status DeQueue_L(LinkQueue &Q, QElemType_L &e) {QueuePtr p;if(Q.front==Q.rear)return ERROR;p = Q.front->next;e = p->data;Q.front->next = p->next;if(Q.rear==p)Q.rear = Q.front;free(p);return OK; }

單鏈隊列操作實例及代碼：

代碼：

#include<cstdio> #include<cstdlib>#define OK 1 #define ERROR 0 #define OVERFLOW -2 #define UNDERFLOW -3 #define TRUE 1 #define FALSE 0typedef int QElemType_L; typedef int Status;typedef struct QNode {QElemType_L data;struct QNode *next; }QNode; typedef QNode* QueuePtr; typedef struct {QueuePtr front; QueuePtr rear; }LinkQueue; Status InitQueue_L(LinkQueue &Q) {Q.front = Q.rear = (QueuePtr)malloc(sizeof(QNode));if(!Q.front)exit(OVERFLOW);Q.front->next = NULL;return OK; } void ClearQueue_L(LinkQueue &Q) {Q.rear = Q.front->next;while(Q.rear){Q.front->next = Q.rear->next; free(Q.rear); Q.rear = Q.front->next;}Q.rear = Q.front; } void DestroyQueue_L(LinkQueue &Q) {while(Q.front){Q.rear = Q.front->next;free(Q.front);Q.front = Q.rear; } } Status EnQueue_L(LinkQueue &Q, QElemType_L e) {QueuePtr p;p = (QueuePtr)malloc(sizeof(QNode));if(!p)exit(OVERFLOW);p->data = e;p->next = NULL;Q.rear->next = p;Q.rear=p;return OK; } Status DeQueue_L(LinkQueue &Q, QElemType_L &e) {QueuePtr p;if(Q.front==Q.rear)return ERROR;p = Q.front->next;e = p->data;Q.front->next = p->next;if(Q.rear==p)Q.rear = Q.front;free(p);return OK; } void QueueTraverse_L(LinkQueue Q, void (Visit)(QElemType_L)) {QueuePtr p;p = Q.front->next;while(p){Visit(p->data);p = p->next;}printf("\n"); } void PrintElem(QElemType_L e) {printf("%d ", e); } Status QueueEmpty_L(LinkQueue Q) {if(Q.front==Q.rear)return TRUE;elsereturn FALSE; } int main(){LinkQueue Q;int i;QElemType_L e;printf("初始化鏈隊 Q ...\n"); InitQueue_L(Q);printf("\n");QueueEmpty_L(Q) ? printf(" Q 為空！！\n") : printf(" Q 不為空！\n");printf("\n");for(i=1; i<=6; i++) {printf("元素 \"%2d\" 入隊，", 2*i);EnQueue_L(Q, 2*i);printf("\n");}printf("\n");printf(" Q 中的元素為：Q = "); QueueTraverse_L(Q, PrintElem);printf("\n");DeQueue_L(Q, e);printf("隊頭元素 \"%d\" 出隊...\n", e);printf(" Q 中的元素為：Q = "); QueueTraverse_L(Q, PrintElem);printf("\n"); printf("銷毀 Q 前：");Q.front!=NULL && Q.rear!=NULL ? printf(" Q 存在！\n") : printf(" Q 不存在！！\n");DestroyQueue_L(Q);printf("銷毀 Q 后：");Q.front!=NULL && Q.rear!=NULL ? printf(" Q 存在！\n") : printf(" Q 不存在！！\n");printf("\n"); }

輸出：

初始化鏈隊 Q …

Q 為空！！

元素 " 2" 入隊，
元素 " 4" 入隊，
元素 " 6" 入隊，
元素 " 8" 入隊，
元素 “10” 入隊，
元素 “12” 入隊，

Q 中的元素為：Q = 2 4 6 8 10 12

隊頭元素 “2” 出隊…
Q 中的元素為：Q = 4 6 8 10 12

銷毀 Q 前： Q 存在！
銷毀 Q 后： Q 不存在！！

總結

以上是生活随笔為你收集整理的数据结构：单链队列的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。