꧁ 各位大佬们好！很荣幸能够得到您的访问，让我们一起在编程道路上任重道远！꧂
☙ 博客专栏：【数据结构初阶】❧
⛅ 本篇内容简介：数据结构初阶中的队列的实现以及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);
}

? 结束语

? 相隔千里，不能陪各位大佬在中秋节一起赏月，但是我们还能看到同一个月亮。中秋节祝各位大佬中秋快乐。

【写在最后·想告诉你】

在互联网这个行业里

任何时候都要学好技术

永远都是技术为王

原文链接：https://blog.csdn.net/qq_63938813/article/details/126788918