leetcode225. 用队列实现栈

1.题目描述：

2.解法：

与leetcode232. 用栈实现队列不同，无法用两个队列模仿出栈入栈，queue2用来存放从queue1弹出的元素，等queue1队列最末元素弹出后再将queue2存储的元素重新放回queue1。

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

    }
    
    public void push(int x) {
        queue1.offer(x);
    }
    
    public int pop() {
        int res = 0;
        while (!queue1.isEmpty()) {
            Integer temp = queue1.poll();
            if (queue1.isEmpty()) res = temp.intValue();
            else queue2.offer(temp);
        }
        while (!queue2.isEmpty()) {
            queue1.offer(queue2.poll());
        }
        return res;
    }
    
    public int top() {
        int res = 0;
        while (!queue1.isEmpty()) {
            Integer temp = queue1.poll();
            if (queue1.isEmpty()) res = temp.intValue();
            queue2.offer(temp);
        }
        while (!queue2.isEmpty()) {
            queue1.offer(queue2.poll());
        }
        return res;
    }
    
    public boolean empty() {
        return queue1.isEmpty();
    }

}

使用单个队列：将queue2中存储的元素直接循环添加到queue1中。 

class MyStack {
    Queue queue = new LinkedList<>();
    public MyStack() {

    }
    
    public void push(int x) {
        queue.offer(x);
    }
    
    public int pop() {
        int res = 0;
        int size = queue.size();//这里需要借助size判断，使用isEmpty会死循环
        while (size > 0) {
            Integer temp = queue.poll();
            if (size == 1) res = temp.intValue();
            else queue.offer(temp);
            size--; 
        }
        return res;
    }
    
    public int top() {
        int res = 0;
        int size = queue.size();
        while (size > 0) {
            Integer temp = queue.poll();
            if (size == 1) res = temp.intValue();
            queue.offer(temp);
            size--; 
        }
        return res;
    }
    
    public boolean empty() {
        return queue.isEmpty();
    }
}

注：也可以使用Deque双向队列简化

增：deque.offerFirst()， deque.offerLast()；从头添加和尾部添加

删：deque.pollFirst()， deque.pollLast()；从头添加和尾部出队

查：deque.peekFirst(), deque.peekLast()；查看头添加和尾部元素