【栈】化栈为队（实现push、pop、peak、empty等操作）

小咪咪 2022-10-18 15:57 116阅读 0赞

## 一、题目 ##

实现一个MyQueue类，该类用两个栈来实现一个队列。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dqaW5qaWU_size_16_color_FFFFFF_t_70]

## 二、分析 ##

本题是 [两栈实现队列][Link 1] 的加强版，在原来只实现push和pop的基础上，新增了实现peak()和empty()的要求。思路还是一样，可以先参考之前的题解，在来看这一题就简单多了。

需要注意的是：本题没有说明当队列中没有元素时，如果执行pop()，应该返回什么。考虑到代码的完整性，这里我默认返回的是-1。

## 三、题解 ##

C++实现如下：

class MyQueue { 
    public:
        /** Initialize your data structure here. */
        stack<int> stack1;
        stack<int> stack2;
    
        MyQueue() { 
    
        }
        
        /** Push element x to the back of queue. */
        void push(int x) { 
            stack1.push(x);
        }
        
        /** Removes the element from in front of queue and returns that element. */
        int pop() { 
            if(!stack2.empty()){ 
                int ans = stack2.top();
                stack2.pop();
                return ans;
            }
            else{ 
                if(!stack1.empty()){ 
                    while(!stack1.empty()){ 
                        stack2.push(stack1.top());
                        stack1.pop();;
                    }
                    int ans = stack2.top();
                    stack2.pop();
                    return ans;
                }
                else{ 
                    return -1;  //当队列是空的时候，返回-1
                }
            }
        }
        
        /** Get the front element. */
        int peek() { 
            if(!stack2.empty()){ 
                return stack2.top();
            }
            else{ 
                if(!stack1.empty()){ 
                    while(!stack1.empty()){ 
                        stack2.push(stack1.top());
                        stack1.pop();
                    }
                    return stack2.top();
                }
                else{ 
                    return -1; //当队列是空的时候，返回-1
                }
            }
        }
        
        /** Returns whether the queue is empty. */
        bool empty() { 
                return stack1.empty() && stack2.empty();
            }
    };

提交结果如下：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dqaW5qaWU_size_16_color_FFFFFF_t_70 1]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dqaW5qaWU_size_16_color_FFFFFF_t_70]: /images/20221005/faf33ef317714b1bb05108fece7c081e.png
[Link 1]: https://leetcode-cn.com/problems/yong-liang-ge-zhan-shi-xian-dui-lie-lcof/solution/si-lu-qing-xi-ji-hu-shuang-bai-by-aijun-3bcg/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dqaW5qaWU_size_16_color_FFFFFF_t_70 1]: /images/20221005/79e499d4428242a390c9d1cfe74f5147.png