【算法专题--栈】用栈实现队列 -- 高频面试题（图文详解，小白一看就懂！！）

目录

一、前言

二、题目描述 

三、解题方法

⭐双栈 模拟 队列

🥝栈 和 队列 的特性 

🍍具体思路

🍍案例图解

四、总结与提炼 

五、共勉   

---

一、前言

        用栈实现队列 这道题，可以说是--栈专题--，最经典的一道题，也是在面试中频率最高的一道题目，通常在面试中，面试官可能会从多个方面考察这道题目，所以大家需要对这道题目非常熟悉哦！！
       本片博客就来详细的讲讲解一下 用栈实现队列 的实现方法，让我们的面试变的更加顺利！！！

二、题目描述 

题目链接： 232. 用栈实现队列 - 力扣（LeetCode）

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

三、解题方法

⭐双栈 模拟 队列

🥝栈 和 队列 的特性 

---

队列的特性是 FIFO（先入先出），而栈的特性是 FILO（先入后出）。

知道两者特性之后，我们需要用两个栈来模拟队列的特性，一个栈为入队栈，一个栈为出对栈。

---

🍍具体思路

---

我们使用两个栈，其中栈 stk1用于入队，另一个栈 stk2 用于出队。 

• 入队时，直接将元素入栈 stk1。时间复杂度 O(1)。 
• 出队时，先判断栈 stk2 是否为空，如果为空，则将栈 stk1 中的元素全部出栈并入栈 stk2，然后再从栈 stk2 中出栈一个元素。如果栈 stk2 不为空，则直接从栈 stk2 中出栈一个元素。时间复杂度 O(1)。
• 获取队首元素时，先判断栈 stk2 是否为空，如果为空，则将栈 stk1 中的元素全部出栈并入栈 stk2，然后再从栈 stk2 中获取栈顶元素。如果栈 stk2 不为空，则直接从栈 stk2 中获取栈顶元素。时间复杂度 O(1)。
• 判断队列是否为空时，只要判断两个栈是否都为空即可。时间复杂度 O(1)。 

干涩的语言可能让大家不太好理解，我们在来看一下 详细的图解

---

🍍案例图解

执行语句：
queue.push(1);
queue.push(2);
queue.pop(); 注意此时的输出栈的操作
queue.push(3);
queue.push(4);
queue.pop();
queue.pop();注意此时的输出栈的操作
queue.pop();
queue.empty();

 我们，根据这些语句，进行 入队 和 出队 的操作

• 首先 需要 入队列 【1】 【2】

• 出 队列  将【1】 从队列 中 排出去 

• 继续 入队列元素 【3】 【4】

•  清空队列中的元素

•  最后，判断队列是否为 空

---

 代码：

class MyQueue {
public:MyQueue() {// 程序自己创建构造函数初始化}void move()  // 移动两个栈 中的 元素{if(st2.empty()){while(!st1.empty()){st2.push(st1.top());st1.pop();}}}void push(int x) // 入 队列{// 将全部元素 入st1 st1.push(x);}int pop()  // 出 队列{// 先 移动 元素move();int ans = st2.top();st2.pop();return ans;}int peek() {move();return st2.top();}bool empty() {return st1.empty() && st2.empty();}private://用两个 栈 实现 队列stack<int> st1;  // 入队stack<int> st2;  // 出队};

四、总结与提炼 

        最后我们来总结一下本文所介绍的内容，本文讲解来一道力扣中有关 用栈实现队列 的题目，这道题目是校招笔试面试中有关栈章节非常高频的一道题目，大家下去一定要自己再画画图，分析一下，把这段代码逻辑自己实现一遍，才能更好地掌握 ！！

五、共勉   

以下就是我对 用栈实现队列 的理解，如果有不懂和发现问题的小伙伴，请在评论区说出来哦，同时我还会继续更新对 栈专题 的理解，请持续关注我哦！！！