---

前言

本文章講述的是數(shù)據(jù)結構的特殊線性表——隊列

---

一.什么是隊列，隊列的特點

隊列是數(shù)據(jù)結構中的一種特殊的線性表，它與棧不同，

隊列的基本圖例如上圖：
顯然，隊列的特點就是:
先進先出
First In First Out
那么我們使用什么樣的方式來實現(xiàn)隊列呢？

基于隊列的特點，使用鏈表而不是數(shù)組來實現(xiàn)隊列是比較合適的
使用數(shù)組來實現(xiàn)隊列的缺點：

出隊時需要挪動數(shù)據(jù)，效率不高。

使用鏈表來實現(xiàn)隊列的優(yōu)點：入隊出隊效率高，不需要挪動數(shù)據(jù)。
使用鏈表來進行入隊出隊時，就需要鏈接起來和釋放節(jié)點，所以我們最好定義頭指針和尾指針指向隊頭和隊尾。

把頭指針和尾指針放在一個結構體中，更方便操作，如下圖：

二、隊列相關操作

隊列的相關操作聲明

void QueueInit(Queue* pq);//初始化隊列void QueueDestroy(Queue* pq);//銷毀隊列void QueuePush(Queue* pq,QDataType x);//插入數(shù)據(jù)void QueuePop(Queue* pq);//刪除數(shù)據(jù)int QueueSize(Queue* pq);//記錄隊列有多少人bool QueueEmpty(Queue* pq);//判斷隊列是否為NULLQDataType QueueFront(Queue* pq);//取出隊頭數(shù)據(jù)QDataType QueueBack(Queue* pq);//取出隊尾數(shù)據(jù)

隊列的創(chuàng)建

#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>typedef int QDataType;
//隊列更適合用鏈表寫,因為如果用順序表來寫，出列的時候需要挪動數(shù)據(jù)typedef struct QueueNode
{QDataType data;struct QueueNode* next;
}QNode;
//隊伍的每個人的結構體typedef struct Queue
{struct QueueNode* head;struct QueueNode* tail;
}Queue;
指向隊頭和隊尾的兩個指針放在一個結構體里面

1.隊列的初始化

void QueueInit(Queue* pq)
{assert(pq);pq->head = pq->tail = NULL;
}

初始化指向隊頭和隊尾的兩個指針為NULL

2.對隊列進行銷毀

void QueueDestroy(Queue* pq)
{assert(pq);QNode* cur = pq->head;while (cur){QNode* next = cur->next;free(cur);cur = next;}pq->head = pq->tail = NULL;
}

3.判斷隊列是否為空隊列

bool QueueEmpty(Queue* pq)
{assert(pq);return pq->head == NULL;
}

4.入隊操作

解讀：隊列的實現(xiàn)方式是鏈表，不需要檢查容量不足，每入隊一個人就申請一個節(jié)點即可

void QueuePush(Queue* pq, QDataType x)
{assert(pq);QNode* newnode = (QNode*)malloc(sizeof(QNode));assert(newnode != NULL);newnode->data = x;newnode->next = NULL;if (pq->head == NULL){pq->head = pq->tail = newnode;}//第一次入隊的時候，就作為隊頭，頭指針指向它pq->tail->next = newnode;pq->tail = newnode;}

5.出隊操作

//記住隊列是先進先出，所以隊頭先出
void QueuePop(Queue* pq)
{assert(pq);assert(!QueueEmpty(pq));//隊頭為空，說明刪完了QNode* newhead = pq->head->next;//先記錄隊頭的下一個人//刪到最后的時候，tail沒有置空，是野指針，所以這里要判斷if (newhead == NULL){pq->tail = NULL;}free(pq->head);pq->head = newhead;
}

6.取出隊頭數(shù)據(jù)

注意出隊的時候，并沒有拿出該人數(shù)的節(jié)點的值

QDataType QueueFront(Queue* pq)
{assert(pq);assert(!QueueEmpty(pq));return pq->head->data;
}

7. 取出隊尾數(shù)據(jù)

QDataType QueueBack(Queue* pq)
{assert(pq);assert(!QueueEmpty(pq));return pq->tail->data;
}

8.計算隊伍的人數(shù)

int QueueSize(Queue* pq)
{assert(pq);int size = 0;QNode* cur = pq->head;while (cur){++size;cur = cur->next;}return size;
}

總結

文章講述簡單隊列的實現(xiàn)，復雜隊列后續(xù)會講。