225. Implement Stack using Queues

,

Queue

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
class MyStack {

    private Queue<Integer> queue;
    private Queue<Integer> queueForAddFirst; // 尽量保持为空

    public MyStack() {
        // 整体思路：保持一个队列为空，每次插入时插入至空队列中，然后将非空队列的所有元素插入至之前的空队列中，以实现 addFirst 功能，后面 poll 时即为最后插入的元素
        this.queue = new LinkedList<>();
        this.queueForAddFirst = new LinkedList<>();
    }

    public void push(int x) {
        queueForAddFirst.offer(x); // 此时该队列为空，x 插入后仅有一个节点

        // 把之前 queue 的元素移动至 queueForAddFirst
        while (!queue.isEmpty()) {
            queueForAddFirst.offer(queue.poll());
        }

        // 到此时 queueForAddFirst 队列中的元素顺序为：刚插入的元素位于队首，之前 queue 的元素在队首后面
        // 将 queueForAddFirst 的元素全部移动至 queue, 保持 queueForAddFirst 为空的状态
        Queue<Integer> tmp = queue;
        queue = queueForAddFirst;
        queueForAddFirst = tmp;
    }

    public int pop() {
        return queue.poll();
    }

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

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

}

Queue

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class MyStack {

    private final Queue<Integer> queue;

    public MyStack() {
        this.queue = new LinkedList<>();
    }

    public void push(int x) {
        int size = queue.size(); // 获取添加前的队列长度
        queue.offer(x); // 添加至队列尾部

        for (int i = size; i > 0; i--) {
            queue.offer(queue.poll()); // 将添加前的元素全部移动至 x 后面，且这部分元素顺序未改变，完成移动后 x 位于队列头部
        }
    }

    public int pop() {
        return queue.poll();
    }

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

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

}

References

225. Implement Stack using Queues