??? ?各位大佬们好！很荣幸能够得到您的访问，让我们一起在编程道路上任重道远！?
??博客专栏：【数据结构初阶】?
? 本篇内容简介：数据结构初阶中的队列的实现以及LeetCode练习！
? 了解作者：励志成为一名编程大牛的学子，目前是大二的编程小白。
?励志术语：编程道路的乏味，让我们一起学习变得有趣！
文章目录
🌔 队列的概念及结构
队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出 FIFO（First in First out）。
入队列：进行插入操作的一端称为队尾。
出队列：进行删除操作的一端称为队头。
🌗 队列的实现
队列可以是数组或者链表的结构实现，但是使用链表的结构实现更优一点。因为如果使用数组的结构，出队列在数组头上的数据，效率会比较低。在这里我们使用链表来实现队列。（数组不适合数组头频繁删除或者数组中插入数据）。
🌒 队列的链式结构
//队列的链式结构
typedef int QDataType;
typedef struct QListNode
{
struct QListNode* next;
QDataType Data;
}QNode;
//队列的结构
typedef struct Queue
{
QNode* front;
QNode* back;
int size;//记录队列节点的个数
}Queue;?🌒 队列的初始化
初始化队列就是要使头指针与尾指针都置为空，将size也置为空。
void QueueInit(Queue* pq)
{
//断言队列不能为空
assert(pq);
pq->front = pq->back = NULL;
pq->size = 0;
}?🌒 队尾入数据
首先我们要先创造新的要插入的节点，1.如果是第一个插入数据，将头指针与尾指针都指向newnode；2.平常的尾插，先将newnode尾插到back指针后，再将back指针指向尾节点。
void QueuePush(Queue* pq, QDataType x)
{
assert(pq);
//先创造节点，再进行链接
QNode* newnode = (QNode*)malloc(sizeof(QNode));
if (newnode == NULL)
{
perror("malloc fail");
exit(-1);
}
//初始化节点
newnode->Data = x;
newnode->next = NULL;
//链接，考虑尾节点是空，还是非空
if (pq->back == NULL)
{
pq->front = pq->back = newnode;
}
else
{
pq->back->next = newnode;
pq->back = newnode;
}
pq->size++;//队列节点++
}?🌒 队头出数据
队头出数据时，当队头为空时就不能再出数据了，需要进行判空处理。
1. 当队列只剩余一个数据时，如果直接free，会造成back的野指针问题，所以我们需要单独判断这种情况。
2. 我们需要记录要删除的节点，再将front指向下一个，最后置空。
void QueuePop(Queue* pq)
{
assert(pq);
//判断只剩一个数据时
if (pq->front == NULL)
{
free(pq->front);
pq->front = pq->back = NULL;
}
else
{
QNode* del = pq->front;
pq->front = pq->front->next;
free(del);
del = NULL;
}
pq->size--;//出数据需要--size
}🌒 获取队头的数据
//获取队头的数据
QDataType QueueFront(Queue* pq)
{
assert(pq);
assert(!QueueEmpty(pq));
return pq->front->Data;
}🌒 获取队尾的数据
//获取队尾的数据
QDataType QueueBack(Queue* pq)
{
assert(pq);
assert(!QueueEmpty(pq));
return pq->back->Data;
}🌒 获取队列有效元素个数
因为我们在队列的结构体中加上了size记录元素个数，所以我们在这里可以直接返回。
//获取队列中有效元素的个数
int QueueSize(Queue* pq)
{
assert(pq);
return pq->size;
}🌒 判断队列是否为空
如果队列为空返回非0值，如果是非空返回0。
//队列的判空
bool QueueEmpty(Queue* pq)
{
assert(pq);
return pq->front == NULL && pq->back == NULL;
}🌒 队列的销毁
因为我们这里使用链表实现，所以我们要将链表的节点，一个一个释放。
//队列的销毁
void QueueDestroy(Queue* pq)
{
assert(pq);
QNode* cur = pq->front;
while (cur != NULL)
{
QNode* del = cur;
cur = cur->next;
free(del);
}
pq->front = pq->back = NULL;
}🌒 测试队列接口功能
int main()
{
Queue q;
QueueInit(&q);
//队尾插入数据
QueuePush(&q, 1);
QueuePush(&q, 2);
QueuePush(&q, 3);
QueuePush(&q, 4);
QueuePush(&q, 5);
while (!QueueEmpty(&q))
{
//获取队头的数据
printf("%d ", QueueFront(&q));
QueuePop(&q);
}
printf("\n");
QueueDestroy(&q);
return 0;
}
?🌔 队列源代码
🌗 Queue.c文件
#include"Queue.h"
void QueueInit(Queue* pq)
{
//断言队列不能为空
assert(pq);
pq->front = pq->back = NULL;
pq->size = 0;
}
void QueuePush(Queue* pq, QDataType x)
{
assert(pq);
//先创造节点，再进行链接
QNode* newnode = (QNode*)malloc(sizeof(QNode));
if (newnode == NULL)
{
perror("malloc fail");
exit(-1);
}
//初始化节点
newnode->Data = x;
newnode->next = NULL;
//链接，考虑尾节点是空，还是非空
if (pq->back == NULL)
{
pq->front = pq->back = newnode;
}
else
{
pq->back->next = newnode;
pq->back = newnode;
}
pq->size++;//队列节点++
}
void QueuePop(Queue* pq)
{
assert(pq);
assert(!QueueEmpty(pq));
//判断只剩一个数据时
if (pq->front == NULL)
{
free(pq->front);
pq->front = pq->back = NULL;
}
else
{
QNode* del = pq->front;
pq->front = pq->front->next;
free(del);
del = NULL;
}
pq->size--;//出数据需要--size
}
//获取队头的数据
QDataType QueueFront(Queue* pq)
{
assert(pq);
assert(!QueueEmpty(pq));
return pq->front->Data;
}
//获取队尾的数据
QDataType QueueBack(Queue* pq)
{
assert(pq);
assert(!QueueEmpty(pq));
return pq->back->Data;
}
//获取队列中有效元素的个数
int QueueSize(Queue* pq)
{
assert(pq);
return pq->size;
}
//队列的判空
bool QueueEmpty(Queue* pq)
{
assert(pq);
return pq->front == NULL && pq->back == NULL;
}
//队列的销毁
void QueueDestroy(Queue* pq)
{
assert(pq);
QNode* cur = pq->front;
while (cur != NULL)
{
QNode* del = cur;
cur = cur->next;
free(del);
}
pq->front = pq->back = NULL;
}🌗 Queue.h文件
#define _CRT_SECURE_NO_WARNINGS 1
#pragma once
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
#include<stdbool.h>
//队列的链式结构
typedef int QDataType;
typedef struct QListNode
{
struct QListNode* next;
QDataType Data;
}QNode;
//队列的结构
typedef struct Queue
{
QNode* front;
QNode* back;
int size;//记录队列节点的个数
}Queue;
//初始化队列
void QueueInit(Queue* pq);
//队尾入数据
void QueuePush(Queue* pq, QDataType x);
//队尾出数据
void QueuePop(Queue* pq);
//获取队头的数据
QDataType QueueFront(Queue* pq);
//获取队尾的数据
QDataType QueueBack(Queue* pq);
//获取队列中有效元素的个数
int QueueSize(Queue* pq);
//队列的判空
bool QueueEmpty(Queue* pq);
//队列的销毁
void QueueDestroy(Queue* pq);🌗 test.c文件
#include"Queue.h"
int main()
{
Queue q;
QueueInit(&q);
//队尾插入数据
QueuePush(&q, 1);
QueuePush(&q, 2);
QueuePush(&q, 3);
QueuePush(&q, 4);
QueuePush(&q, 5);
while (!QueueEmpty(&q))
{
//获取队头的数据
printf("%d ", QueueFront(&q));
QueuePop(&q);
}
printf("\n");
QueueDestroy(&q);
return 0;
}
🌔 225.用队列实现栈
LeeCode题目链接：使用两个栈实现队列。OJ
题目描述：
🌗 题解思路
实现栈的结构：在此之前我们需要队列的结构，不过还好我们在前面实现过一个队列了，这里我们直接用。这里我们定义两个队列，一个q1，一个q2。
?
创造栈：这里我们不能像创造队列一样，
Queue q；
return &q;
因为局部变量出了作用域就销毁，所以我们需要malloc一个栈，并且初始化，再返回。
?
入栈：哪个队列不为空，就往哪个队列入数据。
?
出栈：假设一个队列为空，一个队列不为空，将不为空队列的数据导入为空队列中，至原来不为空的队列还剩一个数据。再记录最后一个数据，并且返回。
?
获取栈顶数据：哪个队列不为空，就获取哪个队列中的队尾的数据。
?
判断栈是否为空：当两个队列都为空时，栈就为空。
?
栈的销毁：因为在栈中，有两个队列，所以先销毁两个队列，再释放栈。
?
?🌗 题解代码
// 两个队列
typedef struct {
Queue q1;
Queue q2;
} MyStack;
MyStack* myStackCreate() {
// 需要malloc obj
MyStack* obj=(MyStack*)malloc(sizeof(MyStack));
//初始化
QueueInit(&obj->q1);
QueueInit(&obj->q2);
return obj;
}
void myStackPush(MyStack* obj, int x) {
//两个不为空就push哪个
if(!QueueEmpty(&obj->q1))
{
//入数据
QueuePush(&obj->q1,x);
}
else{
QueuePush(&obj->q2,x);
}
}
int myStackPop(MyStack* obj) { //要返回栈顶的数据
//Pop不为空队列 假设q1为空
MyStack* empty=&obj->q1;
MyStack* nonempty=&obj->q2;
if(!QueueEmpty(&obj->q1))
{
empty=&obj->q2;
nonempty=&obj->q1;
}
//倒数据 还剩下一个数据
while(QueueSize(nonempty)>1)
{
//不为空队列的头数据
QueuePush(empty,QueueFront(nonempty));
QueuePop(nonempty);
}
//返回栈顶元素
int top=QueueFront(nonempty);
QueuePop(nonempty);
return top;
}
int myStackTop(MyStack* obj) {
//获取不为空的队列的尾数据
if(!QueueEmpty(&obj->q1))
{
return QueueBack(&obj->q1);
}
else{
return QueueBack(&obj->q2);
}
}
bool myStackEmpty(MyStack* obj) {
//两个队列都为空
return QueueEmpty(&obj->q1)&&QueueEmpty(&obj->q2);
}
void myStackFree(MyStack* obj) {
//先销毁队列，再free栈
QueueDestroy(&obj->q1);
QueueDestroy(&obj->q2);
free(obj);
}🌔 232.用栈实现队列
LeetCode题目链接：用两个栈实现队列。OJ
题目描述：
?🌗 题解思路
队列结构：还是一样需要栈的所有接口实现，在这里我们定义两个栈，
一个栈叫Push栈：专门用来队列的插入数据。
另一个栈叫Pop栈：专门用来实现出队列的操作。
?
创造队列：还是一样需要malloc一个队列，并且初始化，最后返回。
?
入队列：直接往Push栈里面插入数据。?
?
出队列：判断需不需要将数据从Push栈中全部导入Pop栈中，如果Pop栈中没有数据，就说明需要倒数据。因为是栈的性质，所以队头的数据就是栈顶的数据，就是倒过去之后栈顶的数据。（需要Pop操作）
?
获取队头的数据：也是一样判断是否需要倒数据，再记录Pop栈顶的数据，返回。（不需要Pop操作）
?
队列的判空：两个栈都为空时，队列就为空。?
?
队列的销毁：先销毁两个栈，再释放队列。
?
🌗 题解代码
typedef struct {
//一个栈用来Push，一个栈用来Pop
Stack PushST;
Stack PopST;
} MyQueue;
MyQueue* myQueueCreate() {
MyQueue* obj = (MyQueue*)malloc(sizeof(MyQueue));
//进行初始化
StackInit(&obj->PushST);
StackInit(&obj->PopST);
return obj;
}
void myQueuePush(MyQueue* obj, int x) {
//直接往PushST的栈入数据
StackPush(&obj->PushST,x);
}
void PushST_To_PopST(MyQueue* obj)
{
if(StackEmpty(&obj->PopST))
{
while(!StackEmpty(&obj->PushST))
{
//倒PushST栈顶的数据
StackPush(&obj->PopST,StackTop(&obj->PushST));
//删除这个数据
StackPop(&obj->PushST);
}
}
}
int myQueuePop(MyQueue* obj) {
//考虑是否倒数据
PushST_To_PopST(obj);
//返回队列开头的数据
int front=StackTop(&obj->PopST);
StackPop(&obj->PopST);
return front;
}
int myQueuePeek(MyQueue* obj) {
//直接返回队列头的数据
PushST_To_PopST(obj);
int front=StackTop(&obj->PopST);
return front;
}
bool myQueueEmpty(MyQueue* obj) {
return StackEmpty(&obj->PushST) && StackEmpty(&obj->PopST);
}
void myQueueFree(MyQueue* obj) {
StackDestroy(&obj->PushST);
StackDestroy(&obj->PopST);
free(obj);
}🌗 结束语
🎈?相隔千里，不能陪各位大佬在中秋节一起赏月，但是我们还能看到同一个月亮。中秋节祝各位大佬中秋快乐。
【写在最后·想告诉你】
在互联网这个行业里
任何时候都要学好技术
永远都是?技术为王
