1. Toy模板网首页
  2. > Toy博客

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

9月前 作者：stackY、 分类：Toy博客 阅读(47) 违法举报

这篇具有很好参考价值的文章主要介绍了栈和队列OJ题：LeetCode--232.用栈实现队列。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

朋友们、伙计们，我们又见面了，今天给大家带来的是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（双端队列）来模拟一个栈，只要是标准的栈操作即可。

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

2.实例演示

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

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栈中有无数据

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

代码演示：


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中的栈顶元素也就是对头的数据：

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

代码演示： 

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中，然后再进行删除即可：

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

代码演示：

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);
*/

今天的博客就分享到这里，喜欢的老铁留下你的三连，感谢感谢！我们下期再见！！ 文章来源地址https://www.toymoban.com/news/detail-453071.html

到了这里，关于栈和队列OJ题：LeetCode--232.用栈实现队列的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处： 如若内容造成侵权/违法违规/事实不符，请点击违法举报进行投诉反馈，一经查实，立即删除！

分享到：
领支付宝红包 赞助服务器费用

相关文章

  • 【创作赢红包】LeetCode：232. 用栈实现队列

    【创作赢红包】LeetCode：232. 用栈实现队列

    🍎道阻且长，行则将至。🍓 🌻算法，不如说它是一种思考方式🍀 算法专栏： 👉🏻123 题目描述 ：请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（push、pop、peek、empty）： 实现 MyQueue 类： void push(int x) 将元素 x 推到队列的末尾 int pop() 从队列

    2023年04月12日
    浏览(41)
  • Day10|LeetCode232.用栈实现队列、LeetCode 225. 用队列实现栈

    Day10|LeetCode232.用栈实现队列、LeetCode 225. 用队列实现栈

    栈和队列理论基础： 队列是先进先出，栈是先进后出。如图所示： 栈和队列是STL（C++标准库）里面的两个数据结构。 栈是以底层容器完成其所有的工作，对外提供统一的接口，底层容器是可插拔的（也就是说我们可以控制使用哪种容器来实现栈的功能）。  栈的内部结构，

    2024年02月14日
    浏览(38)
  • LeetCode 232.用栈实现队列（详解） (๑•̌.•๑)

    LeetCode 232.用栈实现队列（详解） (๑•̌.•๑)

    创建两个栈，一个用于入数据，一个用于出数据。分别是pushST和popST; 1.如果是入数据就直接入进pushST 2.如果是出数据，先检查popST中有无数据，如果有数据，就直接出。如果没数据，就将pushST中的数据放进popST中，再从popST中出数据。 当pushST中的数据入到popST时，数据是顺序的

    2024年01月24日
    浏览(39)
  • Leetcode的AC指南 —— 栈与队列：232.用栈实现队列

    Leetcode的AC指南 —— 栈与队列：232.用栈实现队列

    摘要： **Leetcode的AC指南 —— 栈与队列：232.用栈实现队列 **。题目介绍：请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（push、pop、peek、empty）： 实现 MyQueue 类： void push(int x) 将元素 x 推到队列的末尾 int pop() 从队列的开头移除并返回元素 int

    2024年01月20日
    浏览(42)
  • 【算法与数据结构】232、LeetCode用栈实现队列

    【算法与数据结构】232、LeetCode用栈实现队列

    所有的LeetCode题解索引，可以看这篇文章——【算法和数据结构】LeetCode题解。    思路分析 ：这道题要求我们用栈模拟队列（工作上一定没人这么搞）。程序当中，push函数很好解决，直接将元素push进输入栈当中。pop函数需要实现队列先进先出的操作，而栈是先进后出。只

    2024年02月12日
    浏览(43)

  • 算法训练day9Leetcode232用栈实现队列225用队列实现栈

    https://programmercarl.com/%E6%A0%88%E4%B8%8E%E9%98%9F%E5%88%97%E7%90%86%E8%AE%BA%E5%9F%BA%E7%A1%80.html 见我的博客 https://blog.csdn.net/qq_36372352/article/details/135470438?spm=1001.2014.3001.5501 在push数据的时候，只要数据放进输入栈就好，但在pop的时候，操作就复杂一些， 输出栈如果为空，就把进栈数据全部导

    2024年01月24日
    浏览(58)
  • 栈和队列OJ题：LeetCode--225.用队列实现栈

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

     朋友们、伙计们，我们又见面了，今天给大家带来的是LeetCode--225.用队列实现栈 数 据 结 构 专 栏：数据结构 个    人   主    页 ：stackY、 LeetCode 专  栏 ：LeetCode刷题训练营 LeetCode--225.用队列实现栈：https://leetcode.cn/problems/implement-stack-using-queues/ 目录 1.题目介绍 2.实例演

    2024年02月06日
    浏览(36)
  • 力扣232：用栈实现队列【java语言实现】

    力扣232：用栈实现队列【java语言实现】

            根据题目要求：要用栈实现队列中的相关方法，收先要明确栈和队列的相关特性 栈：   先进后出 队列：先进先出 先让数字1，2，3，4分别依次 进入 栈和队列中，观察一下：         接下来 弹出 一个元素：可以看到：队列中弹出的元素是1，栈中弹出的元素

    2024年02月20日
    浏览(32)
  • 用队列实现栈和用栈实现队列

    用队列实现栈和用栈实现队列

    前面我们实现了栈和队列，其实栈和队列之间是可以相互实现的 下面我们来看一下 用 队列实现栈 和 用栈实现队列 使用两个队列实现一个后入先出（LIFO）的栈，并支持普通栈的全部四种操作（push、top、pop 和 empty） 实现 MyStack 类： void push(int x) 将元素 x 压入栈顶。 int pop

    2023年04月09日
    浏览(33)

  • 算法第10天|232.用栈实现队列225. 用队列实现栈

    力扣链接 题目描述： 请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（ push 、 pop 、 peek 、 empty ）： 实现  MyQueue  类： void push(int x)  将元素 x 推到队列的末尾 int pop()  从队列的开头移除并返回元素 int peek()  返回队列开头的元素 boolean empty(

    2024年02月22日
    浏览(37)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包，优惠每天领

二维码1

领取红包

二维码2

领红包