数据结构之队列详解（包含例题）

一、队列的概念

队列是一种特殊的线性表，特殊之处在于它只允许在表的前端（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);
}