232-用栈实现队列(Implement Queue using Stacks)
发表于：2021-12-03 | 分类： 简单
字数统计: 604 | 阅读时长: 3分钟 | 阅读量：1

原文链接: https://leetcode-cn.com/problems/implement-queue-using-stacks

英文原文

Implement a first in first out (FIFO) queue using only two stacks. The implemented queue should support all the functions of a normal queue (push, peek, pop, and empty).

Implement the MyQueue class:

  • void push(int x) Pushes element x to the back of the queue.
  • int pop() Removes the element from the front of the queue and returns it.
  • int peek() Returns the element at the front of the queue.
  • boolean empty() Returns true if the queue is empty, false otherwise.

Notes:

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

 

Example 1:

Input
["MyQueue", "push", "push", "peek", "pop", "empty"]
[[], [1], [2], [], [], []]
Output
[null, null, null, 1, 1, false]

Explanation
MyQueue myQueue = new MyQueue();
myQueue.push(1); // queue is: [1]
myQueue.push(2); // queue is: [1, 2] (leftmost is front of the queue)
myQueue.peek(); // return 1
myQueue.pop(); // return 1, queue is [2]
myQueue.empty(); // return false

 

Constraints:

  • 1 <= x <= 9
  • At most 100 calls will be made to push, pop, peek, and empty.
  • All the calls to pop and peek are valid.

 

Follow-up: Can you implement the queue such that each operation is amortized O(1) time complexity? In other words, performing n operations will take overall O(n) time even if one of those operations may take longer.

中文题目

请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（push、pop、peek、empty）：

实现 MyQueue 类：

  • void push(int x) 将元素 x 推到队列的末尾
  • int pop() 从队列的开头移除并返回元素
  • int peek() 返回队列开头的元素
  • boolean empty() 如果队列为空，返回 true ；否则，返回 false

 

说明：

  • 你只能使用标准的栈操作 —— 也就是只有 push to top, peek/pop from top, size, 和 is empty 操作是合法的。
  • 你所使用的语言也许不支持栈。你可以使用 list 或者 deque（双端队列）来模拟一个栈，只要是标准的栈操作即可。

 

进阶：

  • 你能否实现每个操作均摊时间复杂度为 O(1) 的队列？换句话说，执行 n 个操作的总时间复杂度为 O(n) ，即使其中一个操作可能花费较长时间。

 

示例：

输入：
["MyQueue", "push", "push", "peek", "pop", "empty"]
[[], [1], [2], [], [], []]
输出：
[null, null, null, 1, 1, false]

解释：
MyQueue myQueue = new MyQueue();
myQueue.push(1); // queue is: [1]
myQueue.push(2); // queue is: [1, 2] (leftmost is front of the queue)
myQueue.peek(); // return 1
myQueue.pop(); // return 1, queue is [2]
myQueue.empty(); // return false

 

提示：

  • 1 <= x <= 9
  • 最多调用 100 次 push、pop、peek 和 empty
  • 假设所有操作都是有效的 （例如，一个空的队列不会调用 pop 或者 peek 操作）

通过代码

官方题解

这篇文章是为初级读者准备的，文章中介绍队列和栈这两种数据结构。

题解

队列是一种 先进先出（first in - first out， FIFO）的数据结构，队列中的元素都从后端（rear）入队（push），从前端（front）出队（pop）。
实现队列最直观的方法是用链表，但在这篇文章里我会介绍另一个方法 - 使用栈。
栈是一种 后进先出（last in - first out， LIFO）的数据结构，栈中元素从栈顶（top）压入（push)，也从栈顶弹出（pop）。
为了满足队列的 FIFO 的特性，我们需要用到两个栈，用它们其中一个来反转元素的入队顺序，用另一个来存储元素的最终顺序。

方法一（使用两个栈 入队 - $O(n)$， 出队 - $O(1)$）

算法

入队（push）

一个队列是 FIFO 的，但一个栈是 LIFO 的。这就意味着最新压入的元素必须得放在栈底。为了实现这个目的，我们首先需要把 s1 中所有的元素移到 s2 中，接着把新元素压入 s2。最后把 s2 中所有的元素弹出，再把弹出的元素压入 s1。

Push an element in queuePush an element in queue
{:width=”539px”}
{:align=”center”}

Figure 1. Push an element in queue
{:align=”center”}

[]
private int front;

public void push(int x) {
    if (s1.empty())
        front = x;
    while (!s1.isEmpty())
        s2.push(s1.pop());
    s2.push(x);
    while (!s2.isEmpty())
        s1.push(s2.pop());
}

复杂度分析

  • 时间复杂度：$O(n)$
    对于除了新元素之外的所有元素，它们都会被压入两次，弹出两次。新元素只被压入一次，弹出一次。这个过程产生了 $4n + 2$ 次操作，其中 $n$ 是队列的大小。由于 压入 操作和 弹出 操作的时间复杂度为 $O(1)$， 所以时间复杂度为 $O(n)$。

  • 空间复杂度：$O(n)$
    需要额外的内存来存储队列中的元素。

出队（pop）

直接从 s1 弹出就可以了，因为 s1 的栈顶元素就是队列的队首元素。同时我们把弹出之后 s1 的栈顶元素赋值给代表队首元素的 front 变量。

Pop an element from queuePop an element from queue
{:width=”539px”}
{:align=”center”}

Figure 2. Pop an element from queue
{:align=”center”}

[]
// Removes the element from the front of queue.
public void pop() {
    s1.pop();
    if (!s1.empty())
        front = s1.peek();
}

复杂度分析

  • 时间复杂度：$O(1)$
  • 空间复杂度：$O(1)$

判断空（empty）

s1 存储了队列所有的元素，所以只需要检查 s1 的是否为空就可以了。

[]
// Return whether the queue is empty.
public boolean empty() {
    return s1.isEmpty();
}

时间复杂度：$O(1)$
空间复杂度：$O(1)$

取队首元素（peek）

在我们的算法中，用了 front 变量来存储队首元素，在每次 入队 操作或者 出队 操作之后这个变量都会随之更新。

[]
// Get the front element.
public int peek() {
  return front;
}

时间复杂度：$O(1)$
队首元素（front）已经被提前计算出来了，同时也只有 peek 操作可以得到它的值。

空间复杂度：$O(1)$

方法二（使用两个栈 入队 - $O(1)$，出队 - 摊还复杂度 $O(1)$）

算法

入队（push）

新元素总是压入 s1 的栈顶，同时我们会把 s1 中压入的第一个元素赋值给作为队首元素的 front 变量。

Push an element in queuePush an element in queue
{:width=”539px”}
{:align=”center”}

Figure 3. Push an element in queue
{:align=”center”}

[]
private Stack<Integer> s1 = new Stack<>();
private Stack<Integer> s2 = new Stack<>();

// Push element x to the back of queue.
public void push(int x) {
    if (s1.empty())
        front = x;
    s1.push(x);
}

复杂度分析

  • 时间复杂度：$O(1)$
    向栈压入元素的时间复杂度为$O(1)$

  • 空间复杂度：$O(n)$
    需要额外的内存来存储队列元素

出队（pop）

根据栈 LIFO 的特性，s1 中第一个压入的元素在栈底。为了弹出 s1 的栈底元素，我们得把 s1 中所有的元素全部弹出，再把它们压入到另一个栈 s2 中，这个操作会让元素的入栈顺序反转过来。通过这样的方式，s1 中栈底元素就变成了 s2 的栈顶元素，这样就可以直接从 s2 将它弹出了。一旦 s2 变空了，我们只需把 s1 中的元素再一次转移到 s2 就可以了。

Pop an element from stackPop an element from stack
{:width=”539px”}
{:align=”center”}

Figure 4. Pop an element from stack
{:align=”center”}

[]
// Removes the element from in front of queue.
public void pop() {
    if (s2.isEmpty()) {
        while (!s1.isEmpty())
            s2.push(s1.pop());
    }
    s2.pop();    
}

复杂度分析

  • 时间复杂度： 摊还复杂度 $O(1)$，最坏情况下的时间复杂度 $O(n)$
    在最坏情况下，s2 为空，算法需要从 s1 中弹出 $n$ 个元素，然后再把这 $n$ 个元素压入 s2，在这里$n$代表队列的大小。这个过程产生了 $2n$ 步操作，时间复杂度为 $O(n)$。但当 s2 非空时，算法就只有 $O(1)$ 的时间复杂度。所以为什么叫做摊还复杂度 $O(1)$ 呢？ 读了下一章你就知道了。

  • 空间复杂度 ：$O(1)$

摊还分析

摊还分析给出了所有操作的平均性能。摊还分析的核心在于，最坏情况下的操作一旦发生了一次，那么在未来很长一段时间都不会再次发生，这样就会均摊每次操作的代价。

来看下面这个例子，从一个空队列开始，依次执行下面这些操作：

$$
push_1, push_2, \ldots, push_n, pop_1, pop_2 \ldots, pop_n
$$

单次 出队 操作最坏情况下的时间复杂度为 $O(n)$。考虑到我们要做 $n$ 次出队操作，如果我们用最坏情况下的时间复杂度来计算的话，那么所有操作的时间复杂度为 $O(n^2)$。

然而，在一系列的操作中，最坏情况不可能每次都发生，可能一些操作代价很小，另一些代价很高。因此，如果用传统的最坏情况分析，那么给出的时间复杂度是远远大于实际的复杂度的。例如，在一个动态数组里面只有一些插入操作需要花费线性的时间，而其余的一些插入操作只需花费常量的时间。

在上面的例子中，出队 操作最多可以执行的次数跟它之前执行过 入队 操作的次数有关。虽然一次 出队 操作代价可能很大，但是每 n 次 入队 才能产生这么一次代价为 n 的 出队 操作。因此所有操作的总时间复杂度为：n(所有的入队操作产生） + 2 * n(第一次出队操作产生） + n - 1(剩下的出队操作产生）， 所以实际时间复杂度为 $O(2*n)$。于是我们可以得到每次操作的平均时间复杂度为 $O(2n/2n)$=$O(1)$。

判断空（empty）

s1 和 s2 都存有队列的元素，所以只需要检查 s1 和 s2 是否都为空就可以了。

[]
// Return whether the queue is empty.
public boolean empty() {
    return s1.isEmpty() && s2.isEmpty();
}

时间复杂度：$O(1)$
空间复杂度：$O(1)$

取队首元素（peek)

我们定义了 front 变量来保存队首元素，每次 入队 操作我们都会随之更新这个变量。当 s2 为空，front 变量就是队首元素，当 s2 非空，s2 的栈顶元素就是队首元素。

[]
// Get the front element.
public int peek() {
    if (!s2.isEmpty()) {
        return s2.peek();
    }
    return front;
}

时间复杂度：$O(1)$
队首元素要么是之前就被计算出来的，要么就是 s2 栈顶元素。因此时间复杂度为 $O(1)$。

空间复杂度：$O(1)$

统计信息

通过次数 提交次数 AC比率
174868 253588 69.0%

提交历史

提交时间 提交结果 执行时间 内存消耗 语言

相似题目

题目 难度
用队列实现栈 简单
设计 栈 队列
上一篇:
233-数字 1 的个数(Number of Digit One)
下一篇:
234-回文链表(Palindrome Linked List)
Powered By Valine
v1.5.1
本文目录
本文目录
  1. 英文原文
  2. 中文题目
  3. 通过代码
  4. 官方题解
  5. 题解
  6. 统计信息
  7. 提交历史
  8. 相似题目
本站总访问量：3504 次 | 本站访客数：2916 人
Copyright © 2020 - 2021 枫奇丶宛南 | Powered by Hexo | Theme Bamboo