LeetCode.225.Implement Stack using Queues 用队列实现栈

题目描述

225 Implement Stack using Queues
https://leetcode-cn.com/problems/implement-stack-using-queues/

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.

Example:

MyStack stack = new MyStack();

stack.push(1);
stack.push(2);
stack.top();   // returns 2
stack.pop();   // returns 2
stack.empty(); // returns false

Notes:

• 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).

---

相似题目

LeetCode.剑指offer.009.用两个栈实现队列
LeetCode.232.Implement Queue using Stacks 用栈实现队列
LeetCode.225.Implement Stack using Queues 用队列实现栈

---

解题过程

两个队列PushO(1)PopO(n)

2个队列模拟栈，其中一个一直是空的。
push：放到非空队列尾部
pop：非空队列前n-1个元素入队到空队列，返回最后一个元素
empty：两个队列都是空则栈空
top：这里有个优化，使用一个成员变量tail保存最后一个入队的元素，top直接返回这个元素。在push和pop时都需要更新tail

push时间复杂度 O(1)，pop时间复杂度 O(n)

private static class MyStack {
    private Queue<Integer> q1;
    private Queue<Integer> q2;
    private Integer tail;

    /** Initialize your data structure here. */
    public MyStack() {
        q1 = new LinkedList<>();
        q2 = new LinkedList<>();
        tail = null;
    }

    /** Push element x onto stack. */
    public void push(int x) {
        if (q1.isEmpty()) {
            q2.offer(x);
        } else {
            q1.offer(x);
        }
        tail = x;
    }

    /** Removes the element on top of the stack and returns that element. */
    public int pop() {
        tail = null;
        Queue<Integer> emptyQueue = q1.isEmpty() ? q1 : q2;
        Queue<Integer> nonEmptyQueue = q1.isEmpty() ? q2 : q1;
        int size = nonEmptyQueue.size();
        for (int i = 0; i < size - 1; i++) {
            tail = nonEmptyQueue.poll();
            emptyQueue.offer(tail);
        }
        return nonEmptyQueue.poll();
    }

    /** Get the top element. */
    public int top() {
        return tail;
    }

    /** Returns whether the stack is empty. */
    public boolean empty() {
        if (q1.isEmpty() && q2.isEmpty()) {
            return true;
        }
        return false;
    }
}

两队队列PushO(n)PopO(1)

两队队列，一个一直为空。
如果想实现 Pop 时间复杂度为O(1)，就得在入队的时候就把数据整理为栈的结构。
push：元素x放到空队列中，再把非空队列依次插入进来，就实现了最后插入的元素在队头
pop：直接非空队列出队

一个队列PushO(1)PopO(n)

一个队列，队列中的元素按 先进先出 的顺序排列。
Push：正常入队
Pop：前n-1个元素循环插入队列末尾，q.offer(q.poll())，第n个元素出队返回

一个队列PushO(n)PopO(1)

一个队列，队列中的元素按 后进先出 的顺序排列，即永远保持队头的元素是最后插入的
Push：插入队列尾部，然后前n-1个元素循环从头部出队后再插入尾部
Pop：直接出队即可

---

GitHub代码

algorithms/leetcode/leetcode/_225_ImplementStackUsingQueues.java
https://github.com/masikkk/algorithms/blob/master/leetcode/leetcode/_225_ImplementStackUsingQueues.java

---