题目

标题和出处

标题：用队列实现栈

出处：225. 用队列实现栈

难度

4 级

题目描述

要求

请你仅使用两个队列实现一个后进先出的栈.The implemented stack should support all the operations of the normal stack（$\text{push}$、$\text{pop}$、$\text{top}$ 和 $\text{empty}$）.

实现 $\text{MyStack}$ 类：

• $\text{void push(int x)}$ 将元素 $\text{x}$ 压入栈顶.
• $\text{int pop()}$ 移除并返回栈顶元素.
• $\text{int top()}$ 返回栈顶元素.
• $\text{boolean empty()}$ 如果栈是空的,返回 $\text{true}$;否则,返回 $\text{false}$.

注意：

• 你只能使用队列的基本操作,Only add elements at the end of the queue、View and delete elements at the head of the queue、The operations of returning the number of elements and judging whether it is empty are valid.
• 你所使用的语言也许不支持队列.You can use a list or a deque to simulate a queue,As long as all operations are standard queue operations.

示例

示例 1：

输入：
$\text{["MyStack", "push", "push", "top", "pop", "empty"]}$
$\text{[[], [1], [2], [], [], []]}$
输出：
$\text{[null, null, null, 2, 2, false]}$
解释：
$\text{MyStack myStack = new MyStack();}$
$\text{myStack.push(1);}$
$\text{myStack.push(2);}$
$\text{myStack.top();}$ // 返回 $\text{2}$
$\text{myStack.pop();}$ // 返回 $\text{2}$
$\text{myStack.empty();}$ // 返回 $\text{False}$

数据范围

• $\text{1}\le \text{x}\le \text{9}$
• 最多调用 $\text{100}$ 次 $\text{push}$、$\text{pop}$、$\text{top}$ 和 $\text{empty}$
• 每次调用 $\text{pop}$ 和 $\text{top}$ 都是有效的

进阶

Can you implement stack using only one queue？

解法一

思路和算法

由于栈的特点是后进先出,So when using a queue to implement a stack,The order of elements within the queue needs to be maintained,Make the first element of the queue the last element to enqueue.

When implemented using two queues,${\text{queue}}_1$ The role of is to store elements,${\text{queue}}_2$ The role is to assist the operation.

In order to realize the function of the stack,Need to ensure that after each push operation,${\text{queue}}_1$ The head element of the queue is always the newly added element.Therefore, the push operation is as follows：

1. Enqueue the element to be added to ${\text{queue}}_2$;

2. 将 ${\text{queue}}_1$ 的全部元素依次出队并入队到 ${\text{queue}}_2$;

3. 将 ${\text{queue}}_1$ 和 ${\text{queue}}_2$ 互换.

完成上述操作后,${\text{queue}}_2$ 为空,${\text{queue}}_1$ The head element of is the newly added element,${\text{queue}}_1$ The rest of the elements and their order remain unchanged.Therefore, the effect of the above operation is in ${\text{queue}}_1$ The head of the team adds a newly added element,${\text{queue}}_1$ The head and tail of the queue correspond to the top and bottom of the stack, respectively.

Because each push operation is maintained ${\text{queue}}_1$ the order of elements within,Therefore, the operation of popping the stack and viewing the top element of the stack can be easily implemented.The pop operation only needs to ${\text{queue}}_1$ The head element of the team can be removed and returned,The operation to view the top element of the stack only needs to return ${\text{queue}}_1$ 的队首元素即可.

由于 ${\text{queue}}_1$ The role of is to store elements,Therefore, it is only necessary to judge whether the stack is empty or not ${\text{queue}}_1$ 是否为空即可.

代码

class MyStack {
    
    Queue<Integer> queue1;
    Queue<Integer> queue2;

    public MyStack() {
    
        queue1 = new ArrayDeque<Integer>();
        queue2 = new ArrayDeque<Integer>();
    }

    public void push(int x) {
    
        queue2.offer(x);
        while (!queue1.isEmpty()) {
    
            queue2.offer(queue1.poll());
        }
        Queue<Integer> temp = queue1;
        queue1 = queue2;
        queue2 = temp;
    }

    public int pop() {
    
        return queue1.poll();
    }

    public int top() {
    
        return queue1.peek();
    }

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

复杂度分析

• 时间复杂度：构造方法的时间复杂度是 $O(1)$,The time complexity of the push operation is $O(n)$,出栈、The time complexity of checking the top element of the stack and judging whether the stack is empty is the same $O(1)$,其中 $n$ is the number of elements in the stack.
  入栈操作需要将 ${\text{queue}}_1$ 的 $n$ 个元素出队,并将 $n+1$ elements are enqueued ${\text{queue}}_2$,共有 $2n+1$ 次操作,每次出队和入队操作的时间复杂度都是 $O(1)$,因此The time complexity of the push operation is $O(n)$.
  出栈、Viewing the top element of the stack and determining whether the stack is empty are regular queue operations,时间复杂度都是 $O(1)$.

• 空间复杂度：$O(n)$,其中 $n$ is the number of elements in the stack.Elements need to be stored using a queue.

解法二

思路和算法

A stack can also be implemented using a queue.

When implemented using a queue,It is also necessary to maintain the order of elements within the queue,Make the first element of the queue the last element to enqueue,Therefore, it is necessary to ensure that after each push operation,The head element is always the newly added element.

There is a difference between a push operation implemented with one queue and a push operation implemented with two queues,Since there is only one queue,All elements need to be stored in the queue.The stack operation is as follows：

1. Count the number of elements in the queue $\text{size}$;

2. Enqueue the element to be added;

3. the front of the queue $\text{size}$ elements are dequeued and enqueued in turn.

完成上述操作后,The head element is the newly added element,The remaining elements and order in the queue are unchanged.So the effect of the above operation is to add the newly added element at the head of the queue,The head and tail of the queue correspond to the top and bottom of the stack, respectively.

出栈操作、The operation of checking the top element of the stack and judging whether the stack is empty is the same as the solution one,Just perform the corresponding operation on the queue.

代码

class MyStack {
    
    Queue<Integer> queue;

    public MyStack() {
    
        queue = new ArrayDeque<Integer>();
    }

    public void push(int x) {
    
        int size = queue.size();
        queue.offer(x);
        for (int i = 0; i < size; i++) {
    
            queue.offer(queue.poll());
        }
    }

    public int pop() {
    
        return queue.poll();
    }

    public int top() {
    
        return queue.peek();
    }

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

复杂度分析

• 时间复杂度：构造方法的时间复杂度是 $O(1)$,The time complexity of the push operation is $O(n)$,出栈、The time complexity of checking the top element of the stack and judging whether the stack is empty is the same $O(1)$,其中 $n$ is the number of elements in the stack.
  Push operations need to be queued $n$ 个元素出队,并将 $n+1$ 个元素入队,共有 $2n+1$ 次操作,每次出队和入队操作的时间复杂度都是 $O(1)$,因此The time complexity of the push operation is $O(n)$.
  出栈、Viewing the top element of the stack and determining whether the stack is empty are regular queue operations,时间复杂度都是 $O(1)$.

• 空间复杂度：$O(n)$,其中 $n$ is the number of elements in the stack.Elements need to be stored using a queue.