leetcode [#225]

目录

• 1. 题目
• 2. 解决方案
• 3. 注意事项

题目

Implement the following operations of a stack using queues.

• push(x) – Push element x onto stack.
• pop() – Removes the element on top of the stack.
• top() – Get the top element.
• empty() – Return whether the stack is empty.

Note

• You must use only standard operations of a queue – which means only push to back, peek/pop from front, size, and is empty operations are valid.
• Depending on your language, queue may not be supported natively. You may simulate a queue by using a list or deque (double-ended queue), as long as you use only standard operations of a queue.
• You may assume that all operations are valid (for example, no pop or top operations will be called on an empty stack).

---

解决方案

class MyStack {
    private LinkedList<Integer> list1 = new LinkedList<>();
    private LinkedList<Integer> list2 = new LinkedList<>();

    // Push element x onto stack.
    public void push(int x) {
        list1.addLast(x);
    }

    // Removes the element on top of the stack.
    public void pop() {
        while (list1.size() > 1){
            list2.addLast(list1.poll());
        }
        list1.poll();
        while (!list2.isEmpty()){
            list1.addLast(list2.poll());
        }
    }

    // Get the top element.
    public int top() {
        int res = 0;
        while (!list1.isEmpty()){
            if(list1.size() == 1){
                res = list1.poll();
                list2.addLast(res);
            } else {
                list2.addLast(list1.poll());
            }
        }
        while (!list2.isEmpty()){
            list1.addLast(list2.poll());
        }
        return res;
    }

    // Return whether the stack is empty.
    public boolean empty() {
        return list1.isEmpty() ? true : false;
    }
}

---

注意事项

1. 使用两个队列实现栈。
2. 思路是：对于push()操作，直接向第一个队列push即可；对于pop()操作，如果第一个队列的大小大于1，则将第一个队列的元素弹出并压入第二个队列，否则，也就是第一个队列只剩下一个元素的时候，直接将其弹出（但不压入第二个队列），最后再把第二个队列所有元素放回第一个队列；对于peek()操作，类似pop()，当第一个队列大小为1的时候，将这个元素的值赋给res，最后把第二个队列所有元素放回第一个队列。