面试题 03.04. 化栈为队

小灰灰 2023-03-13 11:35 11阅读 0赞

# 题目来源 #

[https://leetcode-cn.com/problems/implement-queue-using-stacks-lcci/][https_leetcode-cn.com_problems_implement-queue-using-stacks-lcci]

# 题目描述 #

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

# 题目解析 #

两个栈：  
一个读栈rStack  
一个写栈wStack

当push时

*  直接往wStack压入元素

当pop时：(一个空的队列不会调用 pop 或者 peek 操作)

*  如果rStack为空，将wStack的元素全部压入rStack， 然后rStack.pop第一个元素
 *  如果rStack不为空，rStack.pop第一个元素

当peek时：

*  如果rStack为空，将wStack的元素全部压入rStack， 然后rStack.peek第一个元素
 *  如果rStack不为空，rStack.peek第一个元素

当empty时：

*  必须rStack.empty && wStack.empty

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

![在这里插入图片描述][20200513091614362.png]

[https_leetcode-cn.com_problems_implement-queue-using-stacks-lcci]: https://leetcode-cn.com/problems/implement-queue-using-stacks-lcci/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70]: /images/20230312/f3a5b95d9c924966b87a3437beefa2b5.png
[20200513091614362.png]: /images/20230312/4a39b6a0507546619abb662447afc111.png