【算法专题--栈】用队列实现栈 -- 高频面试题（图文详解，小白一看就懂！！）
目录
一、前言
用队列实现栈 这道题，可以说是--栈专题--，最经典的一道题，也是在面试中频率最高的一道题目，通常在面试中，面试官可能会从多个方面考察这道题目，所以大家需要对这道题目非常熟悉哦！！
本片博客就来详细的讲讲解一下 用队列实现栈 的实现方法，让我们的面试变的更加顺利！！！
二、题目描述
请你仅使用两个队列实现一个后入先出（LIFO）的栈，并支持普通栈的全部四种操作（push、top、pop 和 empty）。
三、解题方法
首先，需要了解一下，栈 和 队列 的 基本概念
⭐两个队列实现栈
🥝解题思路
用两个队列 que1 和 que2 实现 栈 的功能，que2 其实完全就是一个备份的作用，把 que1中除最后一个元素外的其它元素全部备份到 que2 中，然后弹出最后面的元素，再把其他元素从que2 导回 que1。
干涩的语言可能让大家不太好理解，我们在来看一下 详细的图解
🍍案例图解
模拟的队列执行语句如下：
queue.push(1); queue.push(2); queue.pop(); // 注意弹出的操作 queue.push(3); queue.push(4); queue.pop(); // 注意弹出的操作 queue.pop(); queue.pop(); queue.empty();
- 首先，向 que1 中 入队列元素 【1】【2】 ，模拟元素入栈
- 将 que1 中除队尾元素外 的其它元素，转移到 que2，在移除 que1 中的元素【2】
- 移除 que1 中的元素【2】 ，将 que1 赋值给 que2 ，模拟 移除 栈顶元素
- 继续 向 que1 中入队列元素 【3】【4】，模拟入栈
- 模拟 栈 的 pop 删掉元素 【4】【3】【1】，和之前的步骤一样，将【4】之前的元素，转移到 que2 中
- 删除元素【4】，再将 que2 赋值给 que1 ，清空 que2
- 按照 同样的思路 删除 【3】【1】
代码：
class MyStack {
public:
MyStack()
{
// 程序自己创建构造函数进行初始化
}
void push(int x) // 入队列
{
que1.push(x);
}
int pop() // 出队列
{
int size = que1.size();
size--;
while(size--) // 将 que1 导入 que2 ，但是要留下最后一个元素
{
que2.push(que1.front());
que1.pop();
}
int result = que1.front(); // 留下的最后一个元素就是要返回的元素
que1.pop();
que1 = que2; // 在将 que2 赋值给 que1
// 清空 que2
while(!que2.empty())
{
que2.pop();
}
return result;
}
int top() // 取 队顶
{
return que1.back();
}
bool empty() // 判断队列是否为空
{
return que1.empty();
}
private:
queue<int> que1;
queue<int> que2;
};⭐用一个队列实现栈
🍇解题思路
其实这道题目就是用一个队列就够了。
一个队列在模拟栈弹出元素的时候只要将队列头部的元素（除了最后一个元素外） 重新添加到队列尾部，此时在去弹出元素就是栈的顺序了。
🍍案例图解
queue.push(1); queue.push(2); queue.pop(); // 注意弹出的操作 queue.pop();模拟的队列执行语句如上：
- 向 队列 中插入 元素【1】【2】，模拟入栈
- 删除元素【2】，将元素【1】出队列，然后再重新入队列
- 将元素【2】出队列即可 ，模拟栈 删除元素【2】
- 删除 元素【1】同理
代码：
class MyStack {
public:
MyStack()
{
// 程序自己创建构造函数进行初始化
}
void push(int x) // 入队列
{
que.push(x);
}
int pop() // 出队列
{
int size = que.size();
size--; // 保留最后一个元素
while(size--)
{
que.push(que.front());
que.pop();
}
int result = que.front();
que.pop();
return result;
}
int top() // 取 队顶
{
return que.back();
}
bool empty() // 判断队列是否为空
{
return que.empty();
}
private:
queue<int> que;
};
四、总结与提炼
最后我们来总结一下本文所介绍的内容，本文讲解来一道力扣中有关 用队列实现栈 的题目，这道题目是校招笔试面试中有关栈章节非常高频的一道题目，大家下去一定要自己再画画图，分析一下，把这段代码逻辑自己实现一遍，才能更好地掌握 ！！
五、共勉
以下就是我对 用队列实现栈 的理解，如果有不懂和发现问题的小伙伴，请在评论区说出来哦，同时我还会继续更新对 栈专题 的理解，请持续关注我哦！！！
原文地址：https://blog.csdn.net/weixin_45031801/article/details/140082491
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！