leetcode-225-easy

Implement Stack using Queues

Implement a last-in-first-out (LIFO) stack using only two queues. The implemented stack should support all the functions of a normal stack (push, top, pop, and empty).

Implement the MyStack class:

void push(int x) Pushes element x to the top of the stack.
int pop() Removes the element on the top of the stack and returns it.
int top() Returns the element on the top of the stack.
boolean empty() Returns true if the stack is empty, false otherwise.
Notes:

You must use only standard operations of a queue, which means that only push to back, peek/pop from front, size and is empty operations are valid.
Depending on your language, the queue may not be supported natively. You may simulate a queue using a list or deque (double-ended queue) as long as you use only a queue's standard operations.
Example 1:

Input
["MyStack", "push", "push", "top", "pop", "empty"]
[[], [1], [2], [], [], []]
Output
[null, null, null, 2, 2, false]

Explanation
MyStack myStack = new MyStack();
myStack.push(1);
myStack.push(2);
myStack.top(); // return 2
myStack.pop(); // return 2
myStack.empty(); // return False
Constraints:

1 <= x <= 9
At most 100 calls will be made to push, pop, top, and empty.
All the calls to pop and top are valid.
Follow-up: Can you implement the stack using only one queue?

思路一：两个队列，一个用来存储所有值，另外一个队列只存储单个最新的值

    private Queue<Integer> queueFull;
    private Queue<Integer> queueOne;

    public MyStack() {
        queueFull =  new ArrayDeque<>();
        queueOne =  new ArrayDeque<>();
    }

    public void push(int x) {
        queueFull.offer(x);
        queueOne.clear();
        queueOne.offer(x);
    }

    public int pop() {
        int val = queueOne.isEmpty() ? -1 : queueOne.poll();

        int last = -1;
        while (queueFull.size() > 1) {
            last = queueFull.poll();
            queueOne.offer(last);
        }
        queueFull = queueOne;
        queueOne = new ArrayDeque<>();
        if (last != -1) queueOne.offer(last);

        return val;
    }

    public int top() {
        return queueOne.isEmpty() ? -1 : queueOne.peek();
    }

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

思路二：看了一下官方的解法，发现思路不一样，每次用一个队列先入新增值，然后把另外一个队列的所有值入队列。这样的算法会简洁一些