【数据结构】— 『队列』的实现以及LeetCode队列练习题

 ꧁   各位大佬们好!很荣幸能够得到您的访问,让我们一起在编程道路上任重道远!꧂

☙ 博客专栏:【数据结构初阶】

⛅ 本篇内容简介:数据结构初阶中的队列的实现以及LeetCode练习!

⭐ 了解作者:励志成为一名编程大牛的学子,目前是大二的编程小白。

励志术语:编程道路的乏味,让我们一起学习变得有趣!


文章目录

🌔 队列的概念及结构

🌗 队列的实现

🌒 队列的链式结构

 🌒 队列的初始化

 🌒 队尾入数据

 🌒 队头出数据

🌒 获取队头的数据

🌒 获取队尾的数据

🌒 获取队列有效元素个数

🌒 判断队列是否为空

🌒 队列的销毁

🌒 测试队列接口功能

 🌔 队列源代码

🌗 Queue.c文件

🌗 Queue.h文件

🌗 test.c文件

🌔 225.用队列实现栈

🌗 题解思路

 🌗 题解代码

🌔 232.用栈实现队列

 🌗 题解思路

🌗 题解代码

🌗 结束语


🌔 队列的概念及结构

队列:只允许在一端进行插入数据操作,在另一端进行删除数据操作的特殊线性表,队列具有先进先出 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);
}

🌗 结束语

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

【写在最后·想告诉你】

在互联网这个行业里

任何时候都要学好技术

永远都是 技术为王


版权声明:本文为qq_63938813原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。