【数据结构】—— 队列

1、队列的概念

队列是一种先进先出(First In First Out ，FIFO)的数据结构，可以简单理解为排队的概念。在队列中，数据项按照插入的顺序排列，并且只能在队列的一端插入（称为队尾），在另一端删除（称为队头）。

2、队列的结构

入队列：进行插入操作的一端称为队尾
出队列：进行删除操作的一端称为队头

如何选择合适的数据结构实现队列（数组or链表）

在前面学习的顺序表中，我们知道数组只有在尾插和尾删效率高为O(1)，当需要对头部元素操作时效率较低为O(n)。队列的特点是在队尾插入元素，在队头删除元素，序列两端都需要访问，这就导致使用数组实现队列时必定有一端的插入(or删除)效率低，因此不建议使用数组实现队列。

3、队列的链式存储

通过上面的分析，我选择链式存储结构来实现队列。这是因为链式存储结构实现两端的高效访问很简单——只需要增加一个尾指针即可实现两端的O(1)访问

3.1 队列的链式存储结构

定义两个结构体

• QNode：保存队列中节点的元素数据和下一个节点
• Queue：保存头指针、尾指针和队列中有效元素个数

typedef int QDateType;
typedef struct QueueNode
{QDateType val;//当前节点的数据struct QueueNode* next;//当前节点的下一个节点
}QNode;typedef struct Queue
{QNode* phead;//头指针QNode* ptail;//尾指针int size;//记录队列有效元素个数
}Queue;

3.2 队列的常见接口

//初始化
void QueueInit(Queue* pq);
//销毁
void QueueDestroy(Queue* pq);//入队列
void QueuePush(Queue* pq,QDateType x);//出队列
void QueuePop(Queue* pq);
//获取队头元素
QDateType QueueFront(Queue* pq);
//获取队尾元素
QDateType QueueBack(Queue* pq);
//判空
bool QueueEmpty(Queue* pq);
//获取有效元素个数
int QueueSize(Queue* pq);

3.3 队列的接口实现

初始化

头尾指针置空，队列有效元素个数初始化为0

void QueueInit(Queue* pq)
{assert(pq);//哨兵位可选可不选（可以有也可以没有）pq->phead = pq->ptail = NULL;pq->size = 0;
}

判空

直接返回Queue结构体保存的size即可

bool QueueEmpty(Queue* pq)
{assert(pq);return pq->size == 0;
}

入队列

队尾入队步骤

（1）申请新节点并初始化该节点（将x赋值，下一个节点置空）
（2）判断是否存在尾节点（队列是否为空）

• 存在尾节点（队列不为空）：只需将新节点接到队尾，尾指针后移一位即可。
• 不存在尾节点（队列为空）：改变队头和队尾的值即可

（3）队列有效节点个数加1

void QueuePush(Queue* pq, QDateType x)
{assert(pq);QNode* newnode = (QNode*)malloc(sizeof(QNode));//申请新节点if (newnode == NULL){perror("malloc fail");return;}//对新节点初始化newnode->val = x;newnode->next = NULL;//有尾节点（队列不为空）if (pq->ptail){pq->ptail->next = newnode;pq->ptail = newnode;}else{//一个有效节点都没（队列为空）pq->phead = pq->ptail = newnode;}pq->size++;
}

出队列

（1）判空（队列不为空才能出队）
（2）判断队列有效节点的个数

• 一个节点：释放该节点，将头尾指针置空
• 多个节点：定义临时QNode类型变量保存头节点的下一个节点，释放头节点，头节点更新为保存的节点

（3）队列有效节点个数减1

void QueuePop(Queue* pq)
{assert(pq);//三种情况：0个节点，1个节点,多个节点//0个assert(pq->phead);//暴力检查//if (pq->phead == NULL) return;//温柔检查//队列只有1个有效节点if (pq->phead->next==NULL){free(pq->phead);pq->phead = pq->ptail = NULL;}else{//队列有多个有效节点QNode* next = pq->phead->next;free(pq->phead);pq->phead = next;}pq->size--;
}

获取队头元素

断言判断是否存在头节点，如果存在直接返回头节点的值即可

QDateType QueueFront(Queue* pq)
{assert(pq);//这里只能暴力检查assert(pq->phead);return pq->phead->val;
}

获取队尾元素

断言判断是否存在尾节点，如果存在直接返回尾节点的值即可

QDateType QueueBack(Queue* pq)
{assert(pq);//这里只能暴力检查assert(pq->ptail);return pq->ptail->val;
}

获取节点个数

返回size即可

int QueueSize(Queue* pq)
{assert(pq);return pq->size;
}

销毁

遍历删除（释放）所有节点，最后头尾指针悬空，size置0

void QueueDestroy(Queue* pq)
{assert(pq);QNode* cur = pq->phead;while (cur){QNode* next = cur->next;free(cur);cur = next;}pq->phead = pq->ptail = NULL;pq->size = 0;
}

3.4 源代码

.h文件

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
#include<assert.h>
typedef int QDateType;typedef struct QueueNode
{QDateType val;struct QueueNode* next;
}QNode;
入队
为什么需要两个指针
//void QueuePush(QNode** head,QNode** ptail);
//
出队
//void QueuePop(QNode** head);typedef struct Queue
{QNode* phead;QNode* ptail;int size;
}Queue;//初始化
void QueueInit(Queue* pq);
void QueueDestroy(Queue* pq);//入队列
void QueuePush(Queue* pq,QDateType x);//出队列
void QueuePop(Queue* pq);QDateType QueueFront(Queue* pq);
QDateType QueueBack(Queue* pq);
bool QueueEmpty(Queue* pq);
int QueueSize(Queue* pq);

.c文件

#include "Queue.h"//初始化
void QueueInit(Queue* pq)
{assert(pq);//哨兵位可选可不选pq->phead = pq->ptail = NULL;pq->size = 0;
}
//销毁
void QueueDestroy(Queue* pq)
{assert(pq);QNode* cur = pq->phead;while (cur){QNode* next = cur->next;free(cur);cur = next;}pq->phead = pq->ptail = NULL;pq->size = 0;
}//入队列
void QueuePush(Queue* pq, QDateType x)
{assert(pq);QNode* newnode = (QNode*)malloc(sizeof(QNode));if (newnode == NULL){perror("malloc fail");return;}newnode->val = x;newnode->next = NULL;//有尾节点if (pq->ptail){pq->ptail->next = newnode;pq->ptail = newnode;}else{//一个有效节点都没pq->phead = pq->ptail = newnode;}pq->size++;
}//出队列
void QueuePop(Queue* pq)
{assert(pq);//三种情况：0个节点，1个节点,多个节点//0个assert(pq->phead);//暴力检查//if (pq->phead == NULL) return;//温柔检查//1个if (pq->phead->next==NULL){free(pq->phead);pq->phead = pq->ptail = NULL;}else//多个{QNode* next = pq->phead->next;free(pq->phead);pq->phead = next;}pq->size--;
}QDateType QueueFront(Queue* pq)
{assert(pq);//这里只能暴力检查assert(pq->phead);return pq->phead->val;
}
QDateType QueueBack(Queue* pq)
{assert(pq);//这里只能暴力检查assert(pq->ptail);return pq->ptail->val;
}
bool QueueEmpty(Queue* pq)
{assert(pq);return pq->size == 0;
}
int QueueSize(Queue* pq)
{assert(pq);return pq->size;
}

4、队列的顺序存储（循环队列）

虽然队列的一般实现使用链式存储，但是也有一些情况可以使用数组存储，比如循环队列。
具体可以查看这篇博客———循环队列OJ

END