一、隊列的概念

隊列是一種特殊的線性表，特殊之處在于它只允許在表的前端（front）進行刪除操作，而在表的后端（rear）進行插入操作，和棧一樣，隊列是一種操作受限制的線性表。進行插入操作的端稱為隊尾，進行刪除操作的端稱為隊頭。

二、模擬實現順序隊列

我們可以用單鏈表模擬實現順序隊列。

隊列采用的FIFO(first in first out)，新元素（等待進入隊列的元素）總是被插入到鏈表的尾部（對應單鏈表的尾插），而讀取的時候總是從鏈表的頭部開始讀取。每次讀取一個元素，釋放一個元素（對應單鏈表的頭刪）。

對應的接口

注意又提供一種避免使用二級指針的方法，創建一個結構體變量，里面存儲結點，當我們想要改變結構體里面的值，我們就用一級指針即可。

typedef int QDataType;
typedef struct QueueNode
{//用單鏈表模擬實現隊列struct QueueNode* next;QDataType data;
}QNode;//新的避免二級指針的結構體
typedef struct Queue
{QNode* head;QNode* tail;int sz;
}Que;void QueueInit(Que* pq);
void QueueDestory(Que* pq);
void QueuePush(Que* pq, QDataType x);
void QueeuPop(Que* pq);
QDataType QueueFront(Que* pq);
QDataType QueueBack(Que* pq);
bool QueueEmpty(Que* pq);
int QueueSize(Que* pq);

隊列的初始化：

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

隊列的銷毀

注意free過后，也要指向空

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

隊列的插入數據

也就是單鏈表的尾插，同時也要注意當隊列為空時的特殊情況。

void QueuePush(Que* pq,QDataType x)
{//類似于尾插assert(pq);QNode* newnode = (QNode*)malloc(sizeof(QNode));if (newnode == NULL){perror(malloc);exit(-1);}newnode->data = x;newnode->next = NULL;if (pq->head == NULL){pq->head = pq->tail = newnode;pq->sz++;}else{pq->sz++;pq->tail->next = newnode;pq->tail = newnode;}
}

隊列的刪除數據

也就是單鏈表的頭刪，同時也要注意只剩下一個結點刪除后，尾結點指向空的情況

void QueeuPop(Que* pq)
{assert(pq);assert(pq->sz > 0);//頭刪//單獨判斷只剩下一個結點，頭刪后tail是野指針的情況if (pq->head->next == NULL){free(pq->head);pq->head = pq->tail = NULL;pq->sz--;}else{QNode* cur = pq->head;pq->head = pq->head->next;free(cur);pq->sz--;}}

返回隊列頭數據

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

返回隊列尾數據

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

判斷隊列是否為空

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

返回隊列的數據個數

int QueueSize(Que* pq)
{assert(pq);//assert(pq->head);return pq->sz;
}

三、模擬實現循環隊列

622. 設計循環隊列 - 力扣（LeetCode）

這實際上是把隊列空間想象成一個環形空間，環形空間中的存儲單元循環使用，用這種方法管理的隊列也就稱為循環隊列。

注意本題結構較為復雜，必須要畫圖進行解決，這樣就容易考慮到特殊情況，不容易出錯。

本題用數組實現較為簡單，如果用單鏈表實現，那么rear尾結點的前一個不好尋找。

那數組如何實現循環呢？

數組實現循環并不像單鏈表那樣有一個next指針指向頭結點，如果已經走向尾部，可以直接讓頭部的值等于尾部想要的值。

//如何用數組實現循環？
typedef struct {int* a;int front;int rear;int num;
} MyCircularQueue;MyCircularQueue* myCircularQueueCreate(int k) {MyCircularQueue* cur = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));//用k+1個數組空間，便于判斷空和滿的情況。cur->a = (int*)malloc(sizeof(int)*(k+1));cur->front = 0;cur->rear = 0;cur->num = k;return cur;
}bool myCircularQueueIsEmpty(MyCircularQueue* obj) {if(obj->front == obj->rear)return true;elsereturn false;
}bool myCircularQueueIsFull(MyCircularQueue* obj) {//兩種情況都要考慮到！if(obj->front-obj->rear == 1 || obj->rear-obj->front == obj->num)return true;elsereturn false;
}bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {//先判斷是否已經滿if(myCircularQueueIsFull(obj) == true)return false;//假設rear在隊列的尾部if(obj->rear == obj->num){obj->a[obj->rear] = value;obj->rear = 0;}else{obj->a[obj->rear] = value;obj->rear++;}//obj->a[obj->rear] = value;//obj->rear++;//obj->rear %= (obj->num+1);return true;
}bool myCircularQueueDeQueue(MyCircularQueue* obj) {//先判斷是否已經空了if(myCircularQueueIsEmpty(obj) == true){return false;}//假設front在隊列的尾部if(obj->front == obj->num)obj->front = 0;elseobj->front++;//++obj->front;//obj->front %= (obj->num+1);return true;
}int myCircularQueueFront(MyCircularQueue* obj) {if(myCircularQueueIsEmpty(obj) == true)return -1;elsereturn obj->a[obj->front];
}int myCircularQueueRear(MyCircularQueue* obj) {//注意隊尾的rear比數據提前一位數，所以是rear-1//但要考慮rear-1的情況if(myCircularQueueIsEmpty(obj) == true)return -1;if(obj->rear == 0){//需要再創建一個臨時變量，不能改變rear的值int tmp = obj->num;return obj->a[tmp];}// else//     return  obj->a[(obj->rear+obj->num)%(obj->num+1)];return obj->a[obj->rear-1];
}void myCircularQueueFree(MyCircularQueue* obj) {free(obj->a);free(obj);
}

四、用隊列實現棧

225. 用隊列實現棧 - 力扣（LeetCode）

本題要求用兩個隊列實現棧，兩個隊列我們就可以互相倒數據，來滿足題目對棧的需求！

思路：

入隊列：

入不為空的隊列

出隊列：

利用隊列的性質將前n-1個數據放入另一個空的隊列中，刪除剩下一個數據，這樣就完成棧的pop操作！

代碼：

typedef struct {Que q1;Que q2;
} MyStack;MyStack* myStackCreate() {MyStack* cur = (MyStack*)malloc(sizeof(MyStack));//不能忘記初始化QueueInit(&cur->q1);QueueInit(&cur->q2);return cur;
}void myStackPush(MyStack* obj, int x) {//push到不為空的的隊列中if(!QueueEmpty(&obj->q1)){QueuePush(&obj->q1,x);}else{QueuePush(&obj->q2,x);}
}int myStackPop(MyStack* obj) {//先假設q1不為空，q2為空Que* empty = &obj->q1;Que* nonEmpty = &obj->q2;if(!QueueEmpty(&obj->q1)){//如果假設失敗，相反empty = &obj->q2;nonEmpty = &obj->q1;}while(QueueSize(nonEmpty)>1){//開始用函數進行捯數據//從前往后的順序是根據隊列pop的順序定的QueuePush(empty,QueueFront(nonEmpty));QueuePop(nonEmpty);}int top = QueueBack(nonEmpty);QueuePop(nonEmpty);return top;
}int myStackTop(MyStack* obj) {Que* empty = &obj->q1;Que* nonEmpty = &obj->q2;if(!QueueEmpty(&obj->q1)){//如果假設失敗，相反empty = &obj->q2;nonEmpty = &obj->q1;}return QueueBack(nonEmpty);
}bool myStackEmpty(MyStack* obj) {//判斷兩個隊列return QueueEmpty(&obj->q1) && QueueEmpty(&obj->q2);
}void myStackFree(MyStack* obj) {//先對兩個隊列中的鏈表進行freeQueueDestroy(&obj->q1);QueueDestroy(&obj->q2);free(obj);
}

五、用棧實現隊列

232. 用棧實現隊列 - 力扣（LeetCode）

題目描述：

請你僅使用兩個棧實現先入先出隊列。隊列應當支持一般隊列支持的所有操作（push、pop、peek、empty）：

思路：

本題與上一題用隊列實現棧有所差別，可以直接區分push棧和pop棧，如果pop棧為空，就將push棧全部捯到pop棧！

代碼：

typedef struct 
{ST push;ST pop;
} MyQueue;MyQueue* myQueueCreate() {MyQueue* cur = (MyQueue*)malloc(sizeof(MyQueue));SLInit(&cur->push);SLInit(&cur->pop);return cur;
}void myQueuePush(MyQueue* obj, int x) {STPush(&obj->push,x);
}int myQueuePop(MyQueue* obj) {int ret = myQueuePeek(obj);STPop(&obj->pop);return ret;
}int myQueuePeek(MyQueue* obj) {//出棧只能從后往前出//如果pop棧為空，就將push棧全部捯到pop棧！if(STEmpty(&obj->pop)){while(!STEmpty(&obj->push)){STPush(&obj->pop,STTop(&obj->push));STPop(&obj->push);}}int ret = STTop(&obj->pop);return ret;
}bool myQueueEmpty(MyQueue* obj) {//用函數求解return STEmpty(&obj->push) && STEmpty(&obj->pop);
}void myQueueFree(MyQueue* obj) {SLDestroy(&obj->pop);SLDestroy(&obj->push);free(obj);
}