代码随想录算法训练营第十天 | 232. 用栈实现队列、225. 用队列实现栈

232. 用栈实现队列

leetcode
文档讲解
视频讲解

stack1 做输入栈，stack2 做输出栈。重点是 pop、peek 时，如果 stack2 为空，则先将 stack1 中的元素全部倒入 stack2 中。

class MyQueue {
    Stack<Integer> stack1;
    Stack<Integer> stack2;

    public MyQueue() {
        stack1 = new Stack<>();
        stack2 = new Stack<>();
    }

    public void push(int x) {
        stack1.push(x);
    }

    public int pop() {
        if (stack2.isEmpty()) {
            while (!stack1.isEmpty()) {
                stack2.push(stack1.pop());
            }
        }
        return stack2.pop();
    }

    public int peek() {
        if (stack2.isEmpty()) {
            while (!stack1.isEmpty()) {
                stack2.push(stack1.pop());
            }
        }
        int top = stack2.peek();
        return top;
    }

    public boolean empty() {
        return stack1.size() == 0 && stack2.size() == 0;
    }
}

225. 用队列实现栈

leetcode
文档题解
视频题解

queue1 用来存放数据，queue2 在 queue1 腾地方时临时存放 queue1 的数据。

class MyStack {
    Queue<Integer> queue1;
    Queue<Integer> queue2;

    public MyStack() {
        queue1 = new LinkedList<>();
        queue2 = new LinkedList<>();
    }

    // 模拟栈，即先把 queue1 腾至 queue2，把新元素放进去，再把旧元素放回去
    public void push(int x) {
        while (!queue1.isEmpty()) {
            queue2.offer(queue1.remove());
        }
        queue1.offer(x);
        while (!queue2.isEmpty()) {
            queue1.offer(queue2.remove());
        }
    }

    // 因为 queue2 只在 push 时临时存放数据，平常是空的，所以下面操作的都是 queue1
    public int pop() {
        return queue1.remove();
    }

    public int top() {
        return queue1.peek();
    }

    public boolean empty() {
        return queue1.isEmpty();
    }
}