225. 用队列实现栈

leetcode链接：
https://leetcode.cn/problems/implement-stack-using-queues/

题目分析

思路和 用栈实现队列相似，使用两个队列，push的时候，想空的那个队列里面添加数据。

方案一

class MyStack {

    private Deque dequeLeft;
    private Deque dequeRight;
    public MyStack() {
        dequeLeft = new LinkedList<Integer>();
        dequeRight = new LinkedList<Integer>();
    }

    Integer temp = 0;
    public void push(int x) {
        if (dequeLeft.isEmpty()) {
            dequeLeft.offer(x);
            while (!dequeRight.isEmpty()) {
                temp = (Integer) dequeRight.poll();
                dequeLeft.offer(temp);
            }
        } else {
            dequeRight.offer(x);
            while (!dequeLeft.isEmpty()) {
                temp = (Integer) dequeLeft.poll();
                dequeRight.offer(temp);
            }
        }
    }
    
    public int pop() {
        if (!dequeLeft.isEmpty()) {
            return (Integer) dequeLeft.poll();
        } else {
            return (Integer) dequeRight.poll();
        }
    }
    
    public int top() {
        if (!dequeLeft.isEmpty()) {
            return (Integer) dequeLeft.peek();
        } else {
            return (Integer) dequeRight.peek();
        }
    }
    
    public boolean empty() {

        return dequeLeft.isEmpty() && dequeRight.isEmpty();
    }
}

结果

解答成功:
执行耗时:0 ms,击败了100.00% 的Java用户
内存消耗:39.3 MB,击败了54.06% 的Java用户

官方题解

https://leetcode.cn/problems/implement-stack-using-queues/solution/yong-dui-lie-shi-xian-zhan-by-leetcode-solution/

方法二：一个队列实现相关功能

此图片来自于 leetcode 官方。

class MyStack {
    Queue<Integer> queue;

    /** Initialize your data structure here. */
    public MyStack() {
        queue = new LinkedList<Integer>();
    }
    
    /** Push element x onto stack. */
    public void push(int x) {
        int n = queue.size();
        queue.offer(x);
        for (int i = 0; i < n; i++) {
            queue.offer(queue.poll());
        }
    }
    
    /** Removes the element on top of the stack and returns that element. */
    public int pop() {
        return queue.poll();
    }
    
    /** Get the top element. */
    public int top() {
        return queue.peek();
    }
    
    /** Returns whether the stack is empty. */
    public boolean empty() {
        return queue.isEmpty();
    }
}

作者：LeetCode-Solution
链接：https://leetcode.cn/problems/implement-stack-using-queues/solution/yong-dui-lie-shi-xian-zhan-by-leetcode-solution/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。