栈和队列OJ题：LeetCode--232.用栈实现队列

2024-03-01 1015阅读

温馨提示：这篇文章已超过401天没有更新，请注意相关的内容是否还可用！

朋友们、伙计们，我们又见面了，今天给大家带来的是LeetCode--232.用栈实现队列

数据结构专栏：数据结构

个人主页：stackY、

LeetCode 专栏：LeetCode刷题训练营

LeetCode--232.用栈实现队列：https://leetcode.cn/problems/implement-queue-using-stacks/

1.题目介绍

2.实例演示

3.解题思路

3.1创建队列

3.2入列

3.3出列

3.4获取队头元素

3.5优化代码

3.6检测队列是否为空

3.7销毁队列

4.完整代码

1.题目介绍

请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（push、pop、peek、empty）：

实现 MyQueue 类：

1. void push(int x) 将元素 x 推到队列的末尾

2. int pop() 从队列的开头移除并返回元素

3. int peek() 返回队列开头的元素

4. boolean empty() 如果队列为空，返回 true ；否则，返回 false

说明：

你只能使用标准的栈操作 —— 也就是只有 push to top, peek/pop from top, size, 和 is empty 操作是合法的。

你所使用的语言也许不支持栈。你可以使用 list 或者 deque（双端队列）来模拟一个栈，只要是标准的栈操作即可。

2.实例演示

3.解题思路

在做题之前我们先来进行简单的梳理逻辑，要通过两个栈来实现队列的功能，首先得清楚栈和队列都有什么区别，不熟悉的宝子可以去看看数据结构：栈和队列，队列的功能先进先出，而栈的功能是后进先出，那么有两个栈，要实现队列这种先进先出的功能就比较简单了，可以进行数据的转化，要将数据出队列，那么就需要将这个栈中的数据的前n-1个数据先插入到另外的一个栈，然后再将最后的元素出栈即可，这样就实现了队列的出列操作，那么在入列的时候我们是往哪个栈中入数据呢？所以我们的两个栈分别要有他们的功能，一个用来出数据，另外一个用来入数据，这样子就比较方便了。

3.1创建队列

使用两个栈来实现队列的功能，首先我们得写出一个栈，队列的功能是先进先出，栈的功能是后进先出，在创建队列的时候需要有两个栈，然后为队列创建一块空间，并且将两个栈都进行初始化：

实现栈：

//动态栈
typedef int STDataType;
typedef struct Stack
{
	STDataType* a;
	int top;        //栈顶
	int capacity;  //栈的容量
}Stack;
//对栈的初始化
void StackInit(Stack* pst);
//入栈
void StackPush(Stack* pst, STDataType x);
//出栈
void StackPop(Stack* pst);
//获取栈顶元素
STDataType StackTop(Stack* pst);
//获取栈中的有效元素的个数
int StackSize(Stack* pst);
//检测栈是否为空
bool StackEmpty(Stack* pst);
//销毁栈
void StackDestroy(Stack* pst);
//对栈的初始化
void StackInit(Stack* pst)
{
	assert(pst);
	pst->a = NULL;
	//top为-1时，插入一个数据之后top指向的是刚刚插入数据的位置
	//pst->top = -1     
	//top为0时，插入一个数据之后top指向的是刚刚插入数据后面的位置
	pst->top = 0;
	pst->capacity = 0;
}
//入栈
void StackPush(Stack* pst, STDataType x)
{
	assert(pst);
	//检测容量
	if (pst->top == pst->capacity)
	{
		int NewCapacity = pst->capacity == 0 ? 4 : 2 * pst->capacity;
		//当pst->a为NULL时执行的功能是和malloc一样
		STDataType* tmp = (STDataType*)realloc(pst->a, sizeof(STDataType) * NewCapacity);
		if (tmp == NULL)
		{
			perror("realloc fail");
			return;
		}
		pst->a = tmp;
		pst->capacity = NewCapacity;
	}
	//入栈
	pst->a[pst->top] = x;
	pst->top++;
}
//出栈
void StackPop(Stack* pst)
{
	assert(pst);
	//判断栈是否为空
	assert(!StackEmpty(pst));
	//出栈
	pst->top--;
}
//获取栈顶元素
STDataType StackTop(Stack* pst)
{
	assert(pst);
	assert(!StackEmpty(pst));
	//top指向的是栈顶的下一个位置的元素
	return pst->a[pst->top-1];
}
//获取栈中的有效元素的个数
int StackSize(Stack* pst)
{
	assert(pst);
	return pst->top;
}
//检测栈是否为空
bool StackEmpty(Stack* pst)
{
	assert(pst);
	/*if (pst->top == 0)
	{
		return true;
	}
	else
	{
		return false;
	}*/
	return pst->top == 0;
}
//销毁栈
void StackDestroy(Stack* pst)
{
	assert(pst);
	//释放
	free(pst->a);
	pst->a = NULL;
	//重置为0
	pst->top = pst->capacity = 0;
}

创建队列：

typedef struct {
    Stack STPush;  //用来出数据的栈
    Stack STPop;   //用来入数据的栈
} MyQueue;
MyQueue* myQueueCreate() {
    //先为队列开辟一块空间
    MyQueue* obj = (MyQueue*)malloc(sizeof(MyQueue));
    if(obj == NULL)
    {
        perror("malloc fail");
        return NULL;
    }
    //再初始化栈
    StackInit(&obj->STPush);
    StackInit(&obj->STPop);
    return obj;
}

3.2入列

插入数据就非常简单了，直接将数据插入到我们指定的STPush这个栈中：
代码演示：

void myQueuePush(MyQueue* obj, int x) {
    StackPush(&obj->STPush, x);
}

3.3出列

栈的出栈是先进后出，我们有两个栈，因此可以将STPush栈中的前n-1个数据先依次插入到STPop栈中，然后将剩下的最后一个元素，对于队列来说就是队头的数据进行删除即可，但是呢，当第二次删除的时候STPush中没有数据了，这时的STPop中的数据的排列刚好是队列的这种效果，所以可以直接在STPop栈中直接删除即可，所以出列操作需要分两种情况：STPop栈中有无数据

代码演示：

int myQueuePop(MyQueue* obj) {
    //判断STPop是否为空
    if(StackEmpty(&obj->STPop))
    {
        //导数据
        while (StackSize(&obj->STPush) > 1)
		{
			StackPush(&obj->STPop, StackTop(&obj->STPush));
			StackPop(&obj->STPush);
		}
        //保存队头元素
        int top = StackTop(&obj->STPush);
        //删除
        StackPop(&obj->STPush);
        return top;
    }
    else
    {
        int top = StackTop(&obj->STPop);
		StackPop(&obj->STPop);
		return top;
    }
}

3.4获取队头元素

获取队头元素这里就比较有点麻烦了，先要知道队头元素在哪个栈中，由于我们刚开始设定的缘故，队头的数据是在STPop这个栈中的，这时就需要分两种情况，如果STPop为空，这时就要将STPush中的数据全部插入到STPop中，插入过来之后STPop中的栈顶的数据就是对头的数据，如果STPop不为空，就不需要进行导数据，STPop中的栈顶元素也就是对头的数据：

代码演示：

int myQueuePeek(MyQueue* obj) {
    //判断STPop是否为空
    if(StackEmpty(&obj->STPop))
    {
        //全部导过去
        while (!StackEmpty(&obj->STPush))
		{
			StackPush(&obj->STPop, StackTop(&obj->STPush));
			StackPop(&obj->STPush);
		}
    }
    //再取栈顶元素
    return StackTop(&obj->STPop);
}

3.5优化代码

如果将出列和获取队头元素这两个函数合在一起看的话还是有许多相似之处，因此我们可以进行改造，在出列时可以直接复用获取队头元素这个函数，这时表现出来的结果就是将STPush中的所有元素都挪动到STPop中，然后再进行删除即可：

代码演示：

int myQueuePop(MyQueue* obj) {
    /*
    //判断STPop是否为空
    if(StackEmpty(&obj->STPop))
    {
        //导数据
        while (StackSize(&obj->STPush) > 1)
		{
			StackPush(&obj->STPop, StackTop(&obj->STPush));
			StackPop(&obj->STPush);
		}
        //保存队头元素
        int top = StackTop(&obj->STPush);
        //删除
        StackPop(&obj->STPush);
        return top;
    }
    else
    {
        int top = StackTop(&obj->STPop);
		StackPop(&obj->STPop);
		return top;
    }
    */
    //复用
    int front = myQueuePeek(obj);
    //删除
    StackPop(&obj->STPop);
    return front;
}
int myQueuePeek(MyQueue* obj) {
    //判断STPop是否为空
    if(StackEmpty(&obj->STPop))
    {
        //全部导过去
        while (!StackEmpty(&obj->STPush))
		{
			StackPush(&obj->STPop, StackTop(&obj->STPush));
			StackPop(&obj->STPush);
		}
    }
    //再取栈顶元素
    return StackTop(&obj->STPop);
}

3.6检测队列是否为空

队列若为空就表示两个栈都为空，若一个栈不为空，则队列就不为空：

代码演示：

bool myQueueEmpty(MyQueue* obj) {
    return StackEmpty(&obj->STPush)
		&& StackEmpty(&obj->STPop);
}

3.7销毁队列

要销毁队列先要销毁两个栈，然后再将队列释放：

代码演示：

void myQueueFree(MyQueue* obj) {
    //先释放栈
    StackDestroy(&obj->STPush);
    StackDestroy(&obj->STPop);
    //再释放队列
    free(obj);
}

4.完整代码

//动态栈
typedef int STDataType;
typedef struct Stack
{
	STDataType* a;
	int top;        //栈顶
	int capacity;  //栈的容量
}Stack;
//对栈的初始化
void StackInit(Stack* pst);
//入栈
void StackPush(Stack* pst, STDataType x);
//出栈
void StackPop(Stack* pst);
//获取栈顶元素
STDataType StackTop(Stack* pst);
//获取栈中的有效元素的个数
int StackSize(Stack* pst);
//检测栈是否为空
bool StackEmpty(Stack* pst);
//销毁栈
void StackDestroy(Stack* pst);
//对栈的初始化
void StackInit(Stack* pst)
{
	assert(pst);
	pst->a = NULL;
	//top为-1时，插入一个数据之后top指向的是刚刚插入数据的位置
	//pst->top = -1     
	//top为0时，插入一个数据之后top指向的是刚刚插入数据后面的位置
	pst->top = 0;
	pst->capacity = 0;
}
//入栈
void StackPush(Stack* pst, STDataType x)
{
	assert(pst);
	//检测容量
	if (pst->top == pst->capacity)
	{
		int NewCapacity = pst->capacity == 0 ? 4 : 2 * pst->capacity;
		//当pst->a为NULL时执行的功能是和malloc一样
		STDataType* tmp = (STDataType*)realloc(pst->a, sizeof(STDataType) * NewCapacity);
		if (tmp == NULL)
		{
			perror("realloc fail");
			return;
		}
		pst->a = tmp;
		pst->capacity = NewCapacity;
	}
	//入栈
	pst->a[pst->top] = x;
	pst->top++;
}
//出栈
void StackPop(Stack* pst)
{
	assert(pst);
	//判断栈是否为空
	assert(!StackEmpty(pst));
	//出栈
	pst->top--;
}
//获取栈顶元素
STDataType StackTop(Stack* pst)
{
	assert(pst);
	assert(!StackEmpty(pst));
	//top指向的是栈顶的下一个位置的元素
	return pst->a[pst->top-1];
}
//获取栈中的有效元素的个数
int StackSize(Stack* pst)
{
	assert(pst);
	return pst->top;
}
//检测栈是否为空
bool StackEmpty(Stack* pst)
{
	assert(pst);
	/*if (pst->top == 0)
	{
		return true;
	}
	else
	{
		return false;
	}*/
	return pst->top == 0;
}
//销毁栈
void StackDestroy(Stack* pst)
{
	assert(pst);
	//释放
	free(pst->a);
	pst->a = NULL;
	//重置为0
	pst->top = pst->capacity = 0;
}
typedef struct {
    Stack STPush;  //用来出数据的栈
    Stack STPop;   //用来入数据的栈
} MyQueue;
MyQueue* myQueueCreate() {
    //先为队列开辟一块空间
    MyQueue* obj = (MyQueue*)malloc(sizeof(MyQueue));
    if(obj == NULL)
    {
        perror("malloc fail");
        return NULL;
    }
    //再初始化栈
    StackInit(&obj->STPush);
    StackInit(&obj->STPop);
    return obj;
}
void myQueuePush(MyQueue* obj, int x) {
    StackPush(&obj->STPush, x);
}
int myQueuePop(MyQueue* obj) {
    /*
    //判断STPop是否为空
    if(StackEmpty(&obj->STPop))
    {
        //导数据
        while (StackSize(&obj->STPush) > 1)
		{
			StackPush(&obj->STPop, StackTop(&obj->STPush));
			StackPop(&obj->STPush);
		}
        //保存队头元素
        int top = StackTop(&obj->STPush);
        //删除
        StackPop(&obj->STPush);
        return top;
    }
    else
    {
        int top = StackTop(&obj->STPop);
		StackPop(&obj->STPop);
		return top;
    }
    */
    //复用
    int front = myQueuePeek(obj);
    //删除
    StackPop(&obj->STPop);
    return front;
}
int myQueuePeek(MyQueue* obj) {
    //判断STPop是否为空
    if(StackEmpty(&obj->STPop))
    {
        //全部导过去
        while (!StackEmpty(&obj->STPush))
		{
			StackPush(&obj->STPop, StackTop(&obj->STPush));
			StackPop(&obj->STPush);
		}
    }
    //再取栈顶元素
    return StackTop(&obj->STPop);
}
bool myQueueEmpty(MyQueue* obj) {
    return StackEmpty(&obj->STPush)
		&& StackEmpty(&obj->STPop);
}
void myQueueFree(MyQueue* obj) {
    //先释放栈
    StackDestroy(&obj->STPush);
    StackDestroy(&obj->STPop);
    //再释放队列
    free(obj);
}
/**
 * Your MyQueue struct will be instantiated and called as such:
 * MyQueue* obj = myQueueCreate();
 * myQueuePush(obj, x);
 
 * int param_2 = myQueuePop(obj);
 
 * int param_3 = myQueuePeek(obj);
 
 * bool param_4 = myQueueEmpty(obj);
 
 * myQueueFree(obj);
*/

今天的博客就分享到这里，喜欢的老铁留下你的三连，感谢感谢！我们下期再见！！

VPS购买请点击我

免责声明：我们致力于保护作者版权，注重分享，被刊用文章因无法核实真实出处，未能及时与作者取得联系，或有版权异议的，请联系管理员，我们会立即处理! 部分文章是来自自研大数据AI进行生成,内容摘自(百度百科,百度知道,头条百科,中国民法典,刑法,牛津词典,新华词典,汉语词典,国家院校,科普平台)等数据,内容仅供学习参考,不准确地方联系删除处理! 图片声明：本站部分配图来自人工智能系统AI生成,觅知网授权图片,PxHere摄影无版权图库和百度，360，搜狗等多加搜索引擎自动关键词搜索配图，如有侵权的图片，请第一时间联系我们，邮箱：ciyunidc@ciyunshuju.com。本站只作为美观性配图使用,无任何非法侵犯第三方意图,一切解释权归图片著作权方,本站不承担任何责任。如有恶意碰瓷者,必当奉陪到底严惩不贷!

栈和队列OJ题：LeetCode--232.用栈实现队列

1.题目介绍

2.实例演示

3.解题思路

3.1创建队列

3.2入列

3.3出列

3.4获取队头元素

3.5优化代码

3.6检测队列是否为空

3.7销毁队列

4.完整代码

相关阅读

怎么把织梦的模板替换?

dedecms怎么调用特定的栏目文档?

怎么抓包一个网页?

wap怎么封装app?

目录[+]