目录
前言：
我们前面已经学习了栈，今天我们来学习队列，队列和栈一样，相对来说比较简单，随后，会为大家准备OJ练习题，敬请期待！
一、什么是队列
队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出FIFO(First In First Out)
入队列：进行插入操作的一端称为队尾
出队列：进行删除操作的一 端称为队头
这里简单给大家解释一下：
大家肯定都排过队（别说没有，我不信），大家在排好队先前前进时，是不是先站到队伍里的先走。队列的原理何其类似。因为，你可以猜一猜它为什么叫队列。可用下面图片帮助大家理解。
明白了，基础知识，那就一起来实现一下队列吧。
二、队列的实现
2.1 队列结构
和栈一样，我们队列的结构该如何设计呢？
队列一共有两种结构，分为：顺序结构和链式结构
- 队列的顺序结构
入队，不需要移动任何元素，时间复杂度为O(1)
出队，所有元素需要往前移动，时间复杂度为O(N)
- 队列的链式结构
首先我们定义两个指针，队头指针指向第一个节点，队尾指针指向尾节点
入队（尾插），时间复杂度为O(1)
出队（头删），时间复杂度为O(1)
这里，我们将采取链式结构，如若对顺序结构感兴趣可结合之前的栈进行实现。
我们要采用链式难道要用二级指针吗？一级已经够麻烦了，使用二级会更晕。所以，为了避免这种轻快，我们可采取结构体，如下代码：
typedef int QDataType;
// 链式结构：表示队列
typedef struct QListNode
{
struct QListNode* next;
QDataType data;
}QNode;
// 队列的结构
typedef struct Queue
{
QNode* phead;
QNode* ptatil;
int size;
}Queue;这样即可避免二级指针。
2.2 队列初始化
// 初始化队列
void QueueInit(Queue* q)
{
assert(q);
q->phead = q->ptatil = NULL;
q->size = 0;
}初始化只用将头和尾置为空即可。队列还未建立，所以，先不管。
2.3 队列销毁
// 销毁队列
void QueueDestroy(Queue* q)
{
assert(q);
QNode* cur = q->phead;
while (cur)
{
QNode* next = cur->next;
free(cur);
cur = next;
}
q->phead = q->ptatil = NULL;
q->size = 0;
}销毁时我们要释放的是指针所指向开辟空间，而不是指针本身。所以，使用一个while循来释放。
2.4 入队列
// 队尾入队列
void QueuePush(Queue* q, QDataType data)
{
assert(q);
QNode* newnode = (QNode*)malloc(sizeof(QNode));
if (newnode == NULL)
{
perror("malloc fail");
return;
}
newnode->next = NULL;
newnode->data = data;
if (q->phead == NULL)//这里使用头节点，尾节点判断均可
{
q->phead = q->ptatil = newnode;
}
else
{
q->ptatil->next = newnode;//记住这里是尾节点，不是头节点！！！
q->ptatil = newnode;
}
q->size++;
}入队列时，我们要为其开辟一块空间也就是QNode，这就是队列的元素。要分为两种情况讨论，队列为空和队列不为空。
2.5 出队列
// 队头出队列
void QueuePop(Queue* q)
{
assert(q);
assert(q->size != 0);
if (q->phead->next == NULL)
{
q->phead = q->ptatil = NULL;
}
else
{
QNode* next = q->phead->next;
free(q->phead);
q->phead = next;
}
q->size--;
}要注意：分两种情况进行讨论。
2.6 获取队列头部元素
// 获取队列头部元素
QDataType QueueFront(Queue* q)
{
assert(q);
assert(q->phead);
return q->phead->data;
}这里，直接用头指针返回值即可。
2.7 获取队列尾部元素
// 获取队列队尾元素
QDataType QueueBack(Queue* q)
{
assert(q);
assert(q->ptatil);
return q->ptatil->data;
}和上面一样，运用指针获取值即可。
2.8 获取队列中有效元素个数
int QueueSize(Queue* q)
{
assert(q);
return q->size;
}2.9 检测队列是否为空
// 检测队列是否为空，如果为空返回非零结果，如果非空返回0
bool QueueEmpty(Queue* q)
{
assert(q);
return q->size == 0;
}三、 代码总览
Queue.h
#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
#include<assert.h>
typedef int QDataType;
// 链式结构：表示队列
typedef struct QListNode
{
struct QListNode* next;
QDataType data;
}QNode;
// 队列的结构
typedef struct Queue
{
QNode* phead;
QNode* ptatil;
int size;
}Queue;
// 初始化队列
void QueueInit(Queue* q);
// 队尾入队列
void QueuePush(Queue* q, QDataType data);
// 队头出队列
void QueuePop(Queue* q);
// 获取队列头部元素
QDataType QueueFront(Queue* q);
// 获取队列队尾元素
QDataType QueueBack(Queue* q);
// 获取队列中有效元素个数
int QueueSize(Queue* q);
// 检测队列是否为空，如果为空返回非零结果，如果非空返回0
bool QueueEmpty(Queue* q);
// 销毁队列
void QueueDestroy(Queue* q);
Queue.c
#include"Queue.h"
// 初始化队列
void QueueInit(Queue* q)
{
assert(q);
q->phead = q->ptatil = NULL;
q->size = 0;
}
// 队尾入队列
void QueuePush(Queue* q, QDataType data)
{
assert(q);
QNode* newnode = (QNode*)malloc(sizeof(QNode));
if (newnode == NULL)
{
perror("malloc fail");
return;
}
newnode->next = NULL;
newnode->data = data;
if (q->phead == NULL)
{
q->phead = q->ptatil = newnode;
}
else
{
q->ptatil->next = newnode;//记住这里是尾节点，不是头节点！！！
q->ptatil = newnode;
}
q->size++;
}
// 队头出队列
void QueuePop(Queue* q)
{
assert(q);
assert(q->size != 0);
if (q->phead->next == NULL)
{
q->phead = q->ptatil = NULL;
}
else
{
QNode* next = q->phead->next;
free(q->phead);
q->phead = next;
}
q->size--;
}
// 获取队列头部元素
QDataType QueueFront(Queue* q)
{
assert(q);
assert(q->phead);
return q->phead->data;
}
// 获取队列队尾元素
QDataType QueueBack(Queue* q)
{
assert(q);
assert(q->ptatil);
return q->ptatil->data;
}
// 获取队列中有效元素个数
int QueueSize(Queue* q)
{
assert(q);
return q->size;
}
// 检测队列是否为空，如果为空返回非零结果，如果非空返回0
bool QueueEmpty(Queue* q)
{
assert(q);
return q->size == 0;
}
// 销毁队列
void QueueDestroy(Queue* q)
{
assert(q);
QNode* cur = q->phead;
while (cur)
{
QNode* next = cur->next;
free(cur);
cur = next;
}
q->phead = q->ptatil = NULL;
q->size = 0;
}test.c
#include"Queue.h"
int main()
{
Queue q;
QueueInit(&q);
QueuePush(&q, 1);
QueuePush(&q, 2);
QueuePush(&q, 3);
QueuePush(&q, 4);
while (!QueueEmpty(&q))
{
printf("%d ", QueueFront(&q));
QueuePop(& q);
}
printf("\n");
QueueDestroy(&q);
return 0;
}四、例题
来一道例题来练一练吧！
现有队列Q与栈S，初始时Q中的元素依次是 1,2,3,4,5,6(1在队头)，S 为空。若仅允许下列3种操作:①出队并输出出队元素;②出队并将出队元素入栈;③出栈并输出出栈元素，则不能得到的输出序列是()。
A. 1,2,5,6,4,3 B. 2,3,4,5,6,1 C. 3,4,5,6,1,2 D. 6.5.4.3.2.1
可得：答案为：C。
如果还有什么问题，可以私信也可在评论区留言！
完！
