给大家分享一句我很喜欢我话：
知不足而奋进，望远山而前行！！！
铁铁们，成功的路上必然是孤独且艰难的，但是我们不可以放弃，远山就在前方，但我们能力仍然不足，所有我们更要奋进前行！！！
今天我们更新了队列内容，
🎉 欢迎大家关注🔍点赞👍收藏⭐️留言📝
什么是队列？
队列是一种特殊的线性表，特殊之处在于它只允许在表的前端（head）进行删除操作，而在表的后端（tail）进行插入操作，和栈一样，队列是一种操作受限制的线性表。进行插入操作的端称为队尾，进行删除操作的端称为队头。
这个队列就可以理解成我们平时的排队，先进入的先出去，与我们之前实现的先进后出的栈相反。
用什么来实现栈？
再把上次的图拿出来，我们看看是用线性表来实现队列，还是链表比较好❓
由于我们队列中有多少元素不确定，为了方便，我们使用链表，可以做到需要就直接申请，还有一点就是队列是先进先出，顺序固定，不需要随机访问。所以我们这里实现队列使用链表。
队列的实现
头文件：
#include<stdlib.h>
#include<assert.h>
#include<stdio.h>
#include<stdbool.h>
#include<iostream>
定义结构体：
typedef int QDataType;
typedef struct QueueNode//队列的元素节点
{
struct QueueNode* next;
QDataType val;
}QNode;
typedef struct Queue//队列
{
QNode* phead;
QNode* ptail;
int size;
}Queue;函数声明：
//初始化
void QueueInit(Queue* pq);
//队尾插入
void QueuePush(Queue* pq, QDataType x);
//头删
void QueuePop(Queue* pq);
//获取长度
int QueueSize(Queue* pq);
//队列的销毁
void QueueDestroy(Queue* pq);
//取出队首元素
QDataType QueueFront(Queue* pq);
//取出队尾元素
QDataType QueueBack(Queue* pq);
//判断是否为空
bool QueueEmpty(Queue* pq);函数的实现：
队列的初始化：
//初始化
void QueueInit(Queue* pq)
{
assert(pq);
pq->phead = NULL;
pq->ptail = NULL;
pq->size = 0;
}
初始化还是比较简单的，就是令这个头和尾都为NULL，size=0。
队列的尾插：
//尾插
void QueuePush(Queue* pq, QDataType x)
{
assert(pq);
QNode* newnode = (QNode*)malloc(sizeof(QNode));
if (newnode == NULL)
{
perror("malloc failed!");
exit(0);
}
newnode->next = NULL;
newnode->val = x;
if (pq->ptail == NULL)
{
pq->phead = pq->ptail = newnode;
}
else
{
pq->ptail = pq->ptail->next = newnode;
}
pq->size++;
}
尾插这里我们要注意分为两种情况，一种就是此时这个队列还为空队列，这时就要令ptail和phead都为newnode，然后若不是，那么我们就只令ptail的下一个点等于newnode，然后ptail指向下一个点。
队列的头删：
//头删
void QueuePop(Queue* pq)
{
assert(pq);
assert(pq->size != 0);
//一个节点，防止出现野指针
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--;
}
}头删我们这里也要注意，因为我们这个队列玩意只有一个点，那么我们删除之后可能就会造成ptail为野指针的情况，所以我们这里也要分情况：一种就是如果phead指向NULL，即只有一个节点，所以我们就要free掉phead的同时，还要将两个都置为NULL，另一种情况就只需要关注phead，操作完之后将phead指向下一个点。
获取队列长队：
//获取长度
int QueueSize(Queue* pq)
{
assert(pq);
return pq->size;
}
这里就是我们前面创建对列要加一个size的原因，这样我们就可以方便的知道队列的大小，否则每次想得到队列的大小都要重新计算一遍，浪费更多的时间。
队列的销毁：
//队列的销毁
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;
}队列的销毁也没什么好说的，就是创建一个新的队列，然后循环不断free每一个队列点。
获取队尾元素和队首元素：
//获取队首元素
QDataType QueueFront(Queue* pq)
{
assert(pq);
assert(pq->phead && pq->ptail);//防止为空
return pq->phead->val;
}
//获取队尾元素
QDataType QueueBack(Queue* pq)
{
assert(pq);
assert(pq->phead && pq->ptail);
return pq->ptail->val;
}
这个就是先断言一下，然后直接返回对应的值即可。
判断是否为空：
//判断是否为空
bool QueueEmpty(Queue* pq)
{
assert(pq);
return pq->ptail == NULL;
}这里直接用bool来判断，是就返回true，否则返回false。
完整代码：
Queue.h
#pragma once
#include<stdlib.h>
#include<assert.h>
#include<stdio.h>
#include<stdbool.h>
#include<iostream>
using namespace std;
typedef int QDataType;
typedef struct QueueNode
{
struct QueueNode* next;
QDataType val;
}QNode;
typedef struct Queue
{
QNode* phead;
QNode* ptail;
int size;
}Queue;
//初始化
void QueueInit(Queue* pq);
//队尾插入
void QueuePush(Queue* pq, QDataType x);
//头删
void QueuePop(Queue* pq);
//获取长度
int QueueSize(Queue* pq);
//队列的销毁
void QueueDestroy(Queue* pq);
//取出队首元素
QDataType QueueFront(Queue* pq);
//取出队尾元素
QDataType QueueBack(Queue* pq);
//判断是否为空
bool QueueEmpty(Queue* pq);Queue.cpp:
#include"Queue.h"
//初始化
void QueueInit(Queue* pq)
{
assert(pq);
pq->phead = NULL;
pq->ptail = NULL;
pq->size = 0;
}
//尾插
void QueuePush(Queue* pq, QDataType x)
{
assert(pq);
QNode* newnode = (QNode*)malloc(sizeof(QNode));
if (newnode == NULL)
{
perror("malloc failed!");
exit(0);
}
newnode->next = NULL;
newnode->val = x;
if (pq->ptail == NULL)
{
pq->phead = pq->ptail = newnode;
}
else
{
pq->ptail = pq->ptail->next = newnode;
}
pq->size++;
}
//头删
void QueuePop(Queue* pq)
{
assert(pq);
assert(pq->size != 0);
//一个节点，防止出现野指针
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--;
}
}
//获取长度
int QueueSize(Queue* pq)
{
assert(pq);
return pq->size;
}
//队列的销毁
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;
}
//获取队首元素
QDataType QueueFront(Queue* pq)
{
assert(pq);
assert(pq->phead && pq->ptail);//防止为空
return pq->phead->val;
}
//获取队尾元素
QDataType QueueBack(Queue* pq)
{
assert(pq);
assert(pq->phead && pq->ptail);
return pq->ptail->val;
}
//判断是否为空
bool QueueEmpty(Queue* pq)
{
assert(pq);
return pq->ptail == NULL;
}
test.cpp:
#include"Queue.h"
int main()
{
Queue q;
QueueInit(&q);
QueuePush(&q, 1);
QueuePush(&q, 2);
QueuePush(&q, 3);
QueuePush(&q, 4);
QueuePush(&q, 5);
QueuePop(&q);
while (!QueueEmpty(&q))
{
cout << QueueFront(&q)<<endl;
QueuePop(&q);
}
return 0;
}
