leetcode 232 用栈实现队列

系统管理员 2022-09-10 06:10 106阅读 0赞

## 前言 ##

题目：[232. 用栈实现队列][232.]

参考题解：[用栈实现队列-代码随想录][-]

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

## 提交代码 ##

总思路：队列是先进先出；栈是先进后出；数据先入栈1，弹出到栈2，此时栈2中的数据再弹出时，数据总体满足先进先出。(负负得正)

方法一：两个栈独立使用。第一个栈用于存储数据。但需要peek，pop等操作时候，将第一个栈中的数据弹出到第二个栈中。操作完成后，将剩余数据放回到栈一中。这种思路是，使用一个栈存储数据，一个栈作为队列展示/使用数据。数据总是存储在第一个栈中，保持完整性。

方法二：打通两个栈之间的关系。第一个栈作为输入栈，第二个栈作为输出栈。

> 在push数据的时候，只要数据放进输入栈就好，但在pop的时候，操作就复杂一些，输出栈如果为空，就把进栈数据全部导入进来（注意是全部导入），再从出栈弹出数据，如果输出栈不为空，则直接从出栈弹出数据就可以了。
> 
> 最后如何判断队列为空呢？如果进栈和出栈都为空的话，说明模拟的队列为空了。

### 存储栈-展示栈 ###

class MyQueue {
    private:
        void stackMove(stack<int>& src, stack<int>& target){
            assert(target.empty());
            while(!src.empty()){
                target.push(src.top());
                src.pop();
            }
        }
    
        void clear(stack<int>& st){
            while(!st.empty()) st.pop();
        }
    
        stack<int> st1_data; // 栈1用于存储数据
        stack<int> st2_queue; // 栈2用于作为队列使用
    
    public:
        /** Initialize your data structure here. */
        MyQueue() {
            
        }
        
        /** Push element x to the back of queue. */
        void push(int x) {
            assert(st2_queue.empty());
            st1_data.push(x); // 数据放入
        }
        
        /** Removes the element from in front of queue and returns that element. */
        int pop() {
            assert(st2_queue.empty());
            stackMove(st1_data,st2_queue); // 将栈1中的数据，放入栈2中，作为queue
            int result = st2_queue.top();
            st2_queue.pop(); // 弹出数据
            stackMove(st2_queue,st1_data); // 数据作为queue操作完成后，放回栈1中
            return result;
        }
        
        /** Get the front element. */
        int peek() {
            assert(st2_queue.empty());
            stackMove(st1_data,st2_queue);
            int result = st2_queue.top();
            stackMove(st2_queue,st1_data);
            return result;
        }
        
        /** Returns whether the queue is empty. */
        bool empty() {
            return st1_data.empty();
        }
    };

### 输入栈-输出栈 ###

class MyQueue {
    private:
        stack<int> stIn; // 栈1用于输入
        stack<int> stOut; // 栈2用于输出
    
    public:
        /** Initialize your data structure here. */
        MyQueue() {
            
        }
        
        /** Push element x to the back of queue. */
        void push(int x) {
            stIn.push(x);
        }
        
        /** Removes the element from in front of queue and returns that element. */
        int pop() {
            assert(!this->empty());
            int result;
            if(!stOut.empty()){
                result = stOut.top();
                stOut.pop();
            }else{
                while(!stIn.empty()){
                    stOut.push(stIn.top());
                    stIn.pop();
                }
                result = stOut.top();
                stOut.pop();
            }
            return result;
        }
        
        /** Get the front element. */
        int peek() {
            assert(!this->empty());
            int result =  this->pop();
            stOut.push(result);
            return result;
        }
        
        /** Returns whether the queue is empty. */
        bool empty() {
            return stIn.empty() && stOut.empty();
        }
    };

[232.]: https://leetcode-cn.com/problems/implement-queue-using-stacks/
[-]: https://leetcode-cn.com/problems/implement-queue-using-stacks/solution/dai-ma-sui-xiang-lu-dai-ni-gao-ding-zhan-6ngt/