AcWing 20. 用两个栈实现队列

红太狼 2023-01-11 03:46 63阅读 0赞

**上一篇博客：[AcWing 756. 蛇形矩阵][AcWing 756.]**

>  写在前面：大家好！我是`AC-fun`,我的昵称来自两个单词`Accepted`和`fun`。我是一个热爱ACM的蒟蒻。如果博客中有不足或者的错误的地方欢迎在评论区或者私信我指正，感谢大家的不吝赐教。我的唯一博客更新地址是：[https://ac-fun.blog.csdn.net/][https_ac-fun.blog.csdn.net]。非常感谢大家的支持。一起加油，冲鸭！  
>  `用知识改变命运，用知识成就未来！加油 (ง •̀o•́)ง (ง •̀o•́)ง`

原题链接：[AcWing 20. 用两个栈实现队列][AcWing 20.]

### 文章目录 ###

*  题目信息
 *   *  题目描述
     *  样例
 *  题解
 *   *  解题思路
     *  解题代码

# 题目信息 #

## 题目描述 ##

请用栈实现一个队列，支持如下四种操作：

*  push(x) – 将元素x插到队尾；
 *  pop() – 将队首的元素弹出，并返回该元素；
 *  peek() – 返回队首元素；
 *  empty() – 返回队列是否为空；

注意：

*  你只能使用栈的标准操作：`push to top`，`peek/pop from top`, `size` 和 `is empty`；
 *  如果你选择的编程语言没有栈的标准库，你可以使用list或者deque等模拟栈的操作；
 *  输入数据保证合法，例如，在队列为空时，不会进行`pop`或者`peek`等操作；

## 样例 ##

> MyQueue queue = new MyQueue();  
> queue.push(1);  
> queue.push(2);  
> queue.peek(); // returns 1  
> queue.pop(); // returns 1  
> queue.empty(); // returns false

# 题解 #

## 解题思路 ##

使用两个栈：栈 stk1 用来存储数据，另一个栈 stk2 用来暂存数据。当进行 `push` 操作时，直接将元素 `push` 到 stk1 中即可。当进行 `pop` 操作时将 stk1 中的所有元素都放到 stk2 中，然后将 stk2 的栈顶元素弹出并返回。最后将 stk2 中的元素再放到 stk1 中。`peek` 操作和 `pop` 操作类似，只是不用弹出元素，再将 stk1 中的元素原路返回即可。`empty` 操作只需要判断 stk1 是否为空即可。

## 解题代码 ##

class MyQueue { 
    public:
        stack<int> stk1, stk2;
        /** Initialize your data structure here. */
        MyQueue() { 
            
        }
        
        /** Push element x to the back of queue. */
        void push(int x) { 
            stk1.push(x);
        }
        
        /** Removes the element from in front of queue and returns that element. */
        int pop() { 
            while (!stk1.empty()) { 
                stk2.push(stk1.top());
                stk1.pop();
            }
            int res = stk2.top();
            stk2.pop();
            while (!stk2.empty()) { 
                stk1.push(stk2.top());
                stk2.pop();
            }
            return res;
        }
        
        /** Get the front element. */
        int peek() { 
            while (!stk1.empty()) { 
                stk2.push(stk1.top());
                stk1.pop();
            }
            int res = stk2.top();
            while (!stk2.empty()) { 
                stk1.push(stk2.top());
                stk2.pop();
            }
            return res;
        }
        
        /** Returns whether the queue is empty. */
        bool empty() { 
            return stk1.empty();
        }
    };
    
    /** * Your MyQueue object will be instantiated and called as such: * MyQueue obj = MyQueue(); * obj.push(x); * int param_2 = obj.pop(); * int param_3 = obj.peek(); * bool param_4 = obj.empty(); */

--------------------

> 未完待续，持续更新中……  
> ![20210125213402135.png][]

[AcWing 756.]: https://ac-fun.blog.csdn.net/article/details/112765415
[https_ac-fun.blog.csdn.net]: https://ac-fun.blog.csdn.net/
[AcWing 20.]: https://www.acwing.com/problem/content/36/
[20210125213402135.png]: /images/20221119/83fb7211ead045ada190ecb1da08eb64.png