Problem

Implement a stack by two queues. The queue is first in first out (FIFO). That means you can not directly pop the last element in a queue.

Example
push(1)
pop()
push(2)
isEmpty() // return false
top() // return 2
pop()
isEmpty() // return true

思路

• 维护一个queue只存最后一个元素, 另外一个queue存它前面的元素

class Stack {
    Queue<Integer> q1 = new LinkedList<>();
    Queue<Integer> lastEleQueue = new LinkedList<>();

    // Push a new item into the stack
    public void push(int x) {
        if (lastEleQueue.isEmpty()) {
            lastEleQueue.offer(x);
        } else {
            q1.offer(lastEleQueue.poll());
            lastEleQueue.offer(x);
        }
    }

    // Pop the top of the stack
    public void pop() {
        if (lastEleQueue.isEmpty()) {
            return;
        }
        lastEleQueue.poll();
        int size = q1.size();
        for (int i = 0; i < size - 1; i++) {
            lastEleQueue.offer(q1.poll());
        }
        Queue<Integer> temp = lastEleQueue;
        lastEleQueue = q1;
        q1 = temp;
    }

    // Return the top of the stack
    public int top() {
        return lastEleQueue.peek();
    }

    // Check the stack is empty or not.
    public boolean isEmpty() {
        return lastEleQueue.isEmpty();
    }    
}