算法

014【入门】队列和栈入门题目-栈和队列相互实现

本篇介绍了如何用栈模拟队列（均摊O(1)）和用队列模拟栈。栈模拟队列使用双栈倒数据，需注意倒数据时机和完整性。队列模拟栈，可用双队列或单队列实现，单队列每次push时需将之前元素重排。双端队列ArrayDeque也可高效实现栈。

Posted by Hilda on March 25, 2025

概览

用栈实现队列

题目是：232. 用栈实现队列

请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（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（双端队列）来模拟一个栈，只要是标准的栈操作即可

用队列实现栈

题目是：225. 用队列实现栈

请你仅使用两个队列实现一个后入先出（LIFO）的栈，并支持普通栈的全部四种操作（push、top、pop 和 empty）。

实现 MyStack 类：

void push(int x) 将元素 x 压入栈顶。

int pop() 移除并返回栈顶元素。

int top() 返回栈顶元素。

boolean empty() 如果栈是空的，返回 true ；否则，返回 false 。

注意：

你只能使用队列的基本操作 —— 也就是 push to back、peek/pop from front、size 和 is empty 这些操作

你所使用的语言也许不支持队列。 你可以使用 list （列表）或者 deque（双端队列）来模拟一个队列 , 只要是标准的队列操作即可

力扣-232. 用栈实现队列

232. 用栈实现队列

请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（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（双端队列）来模拟一个栈，只要是标准的栈操作即可。

示例 1：

1
2
3
4
5
6
7
8
9
10
11
12
13

输入：
["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 操作）

进阶：

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

解法1:我自己写的实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51

class MyQueue {
    int N = 100;

    int[] stack1 = new int[N], stack2 = new int[N];
    int size1, size2;

    public MyQueue() {
        size1 = size2 = 0;
    }

    public void push(int x) {
        stack1[size1++] = x;
    }

    public int pop() {
        if (size2 != 0)
            return stack2[--size2];
        if (size1 == 0)
            return 0;// 注意 1 <= x <= 9 所以x=0就是代表没有元素了
        for (int i = size1 - 1; i >= 0; i--) {
            stack2[size2++] = stack1[i];
            size1--;
        }
        return stack2[--size2];
    }

    public int peek() {
        if (size2 != 0)
            return stack2[size2 - 1];
        if (size1 == 0)
            return 0; // 注意 1 <= x <= 9 所以x=0就是代表没有元素了
        for (int i = size1 - 1; i >= 0; i--) {
            stack2[size2++] = stack1[i];
            size1--;
        }
        return stack2[size2 - 1];
    }

    public boolean empty() {
        return size1 == 0 && size2 == 0;
    }
}

/**
 * Your MyQueue object will be instantiated and called as such:
 * MyQueue obj = new MyQueue();
 * obj.push(x);
 * int param_2 = obj.pop();
 * int param_3 = obj.peek();
 * boolean param_4 = obj.empty();
 */

分析：

  • push每次加一个数时间为 O(1)。

  • 当 stack2 为空且需要 pop 或 peek 时，stack1 中的所有元素会被转移到 stack2，时间为 O(n)。但转移后，stack1 变空，stack2 包含所有元素（以相反顺序）。

    关键点：每个元素最多被转移一次——从 stack1 到 stack2。一旦转移到 stack2，它要么被弹出，要么留在那里直到队列变空。

  • 考虑一个包含 n 个操作的序列（例如 n/2 次 push 和 n/2 次 pop）：

    • n/2 次 push：总时间 O(n/2) = O(n)
    • 转移操作：假设所有元素都在某个时刻转移，总共转移 n/2 个元素，花费 O(n/2) = O(n)
    • n/2 次 pop：如果转移发生在某一次 pop，则那次操作花费 O(n)，但之后每次 pop 都是 O(1)，因为 stack2 已填充

    总时间：

    • push：O(n)
    • 转移（总和）：O(n)
    • pop 和 peek 从 stack2 取元素：O(n)

    总时间为 O(n)，n 个操作均摊下来每个操作 O(1)。

所以以上实现：这个队列实现每个操作的均摊时间复杂度为 O(1)。尽管单个 pop 或 peek 操作在最坏情况下可能是 O(n)（当需要转移所有元素时），但通过均摊分析，n 个操作的总时间复杂度为 O(n)。这种方法是经典的“双栈队列”实现，广泛认可其均摊 O(1) 的性能。

解法2:左神的代码

首先左神的思路也是2个栈倒，分为in和out两个栈，但是要注意：

  • 只有out是空才能从in栈中倒到out中，不然会出错。（其实和我上面自己写的思路是一致的，当size2不为0的时候优先返回stack2中的值，当size2=0，那么再看size1，如果size1不为0，则从stack1倒入stack2，然后再pop或者peek，如果size1也等于0，说明此时这个逻辑队列就是空）
  • 如果要倒数据（即从in栈倒到out栈），数据必须要全部倒完。（就是我上面自己写的思路，在pop以及peek中写的循环，i从size1-1到0，全部需要倒过去）

上面提到的关键的2点，在下面的inToOut方法中都有体现了。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49

class MyQueue {

    private Stack<Integer> in;
    private Stack<Integer> out;

    public MyQueue() {
        in = new Stack<>();
        out = new Stack<>();
    }
    // 用来倒数据的
    // 从in栈，把数据倒入out栈
    // 1) out空了，才能倒数据
    // 2) 如果倒数据，in必须倒完
    private void inToOut() {
        if (out.empty()) {
            while (!in.empty()) {
                out.push(in.pop());
            }
        }
    }

    public void push(int x) {
        in.push(x);
        inToOut();
    }

    public int pop() {
        inToOut();
        return out.pop();
    }

    public int peek() {
        inToOut();
        return out.peek();
    }

    public boolean empty() {
        return in.empty() && out.empty();
    }
}

/**
 * Your MyQueue object will be instantiated and called as such:
 * MyQueue obj = new MyQueue();
 * obj.push(x);
 * int param_2 = obj.pop();
 * int param_3 = obj.peek();
 * boolean param_4 = obj.empty();
 */

分析时间复杂度：

每一个数，只有可能进in一次出in一次，进out一次出out一次，所以就是入栈和出栈4次，就是均摊O(1)

225. 用队列实现栈

225. 用队列实现栈

请你仅使用两个队列实现一个后入先出（LIFO）的栈，并支持普通栈的全部四种操作（push、top、pop 和 empty）。

实现 MyStack 类：

  • void push(int x) 将元素 x 压入栈顶。
  • int pop() 移除并返回栈顶元素。
  • int top() 返回栈顶元素。
  • boolean empty() 如果栈是空的，返回 true ；否则，返回 false 。

注意：

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

示例：

1
2
3
4
5
6
7
8
9
10
11
12
13

输入：
["MyStack", "push", "push", "top", "pop", "empty"]
[[], [1], [2], [], [], []]
输出：
[null, null, null, 2, 2, false]

解释：
MyStack myStack = new MyStack();
myStack.push(1);
myStack.push(2);
myStack.top(); // 返回 2
myStack.pop(); // 返回 2
myStack.empty(); // 返回 False

提示：

  • 1 <= x <= 9
  • 最多调用100 次 push、pop、top 和 empty
  • 每次调用 pop 和 top 都保证栈不为空

进阶：你能否仅用一个队列来实现栈。

解法1:临时队列+正式队列

先补充一个Java中LinkedList数据结构的API：

  • poll()：
    • 移除并返回队列的头部元素。
    • 如果队列为空，则返回 null。
    • 不会抛出异常。
  • remove()：
    • 移除并返回队列的头部元素。
    • 如果队列为空，则抛出 NoSuchElementException 异常。
    • 需要捕获异常或者在方法声明中throws该异常

先贴解法：

image-20250325195531478

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

class MyStack {

    private Queue<Integer> queue1;
    private Queue<Integer> queue2;

    public MyStack() {
        queue1 = new LinkedList<>();  // queue1是临时的
        queue2 = new LinkedList<>();  // queue2是正式的
    }

    public void push(int x) {
        queue1.add(x);

        while (!queue2.isEmpty()) {
            queue1.add(queue2.poll());
        }

        while (!queue1.isEmpty()) {
            queue2.add(queue1.poll());
        }
        queue1.clear();
    }

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

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

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

/**
 * Your MyStack object will be instantiated and called as such:
 * MyStack obj = new MyStack();
 * obj.push(x);
 * int param_2 = obj.pop();
 * int param_3 = obj.top();
 * boolean param_4 = obj.empty();
 */

思路是，queue1永远都是临时队列，queue2永远都是正式队列。

每次进来一个数x，先进入queue1，如果queue2是空的，说明此时逻辑栈迎接了第一个元素x，然后直接把x从queue1弹出，弹到queue2即可。如果queue2不是空，那么此时将queue2中的元素以此弹出，进入到queue1的尾巴中。这样就保证了后进先出。然后再将queue1中的元素捯饬到queue2中。每次取数（不管是pop还是peek都是从queue2中）。

解法2:一个队列实现栈

步骤：

  1. 将元素入列到队尾；
  2. 再将除队尾之外的所有元素移除并重写入列。

代码如下：

image-20250325200545919

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

class MyStack {

    Queue<Integer> queue;

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

    public void push(int x) {
        queue.add(x);
        // 除队尾之外的所有元素移除并重写入列
        for (int i = queue.size() - 1; i > 0; i--) {
            queue.add(queue.poll());
        }
    }

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

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

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

/**
 * Your MyStack object will be instantiated and called as such:
 * MyStack obj = new MyStack();
 * obj.push(x);
 * int param_2 = obj.pop();
 * int param_3 = obj.top();
 * boolean param_4 = obj.empty();
 */

解法3:双端队列实现栈

队尾入，队尾出

在 Java 中，双端队列（Double-Ended Queue，简称 Deque）是一个接口，定义在 java.util 包中。它扩展了 Queue 接口，提供了在队列两端（头部和尾部）添加、移除和检查元素的能力。

Java 中的双端队列由 Deque 接口定义，主要实现包括：

  1. ArrayDeque：循环数组实现，高效且常用。
  2. LinkedList：双向链表实现，功能丰富。
  3. ConcurrentLinkedDeque：并发安全的双向链表实现。

其中，ArrayDeque 是最推荐的通用实现，因其 O(1) 的均摊时间复杂度和优异的性能表现。

如果这道力扣225用ArrayDeque实现的话：

image-20250325201158073

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

class MyStack {

    ArrayDeque<Integer> queue;

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

    public void push(int x) {
        queue.addLast(x);
    }

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

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

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

/**
 * Your MyStack object will be instantiated and called as such:
 * MyStack obj = new MyStack();
 * obj.push(x);
 * int param_2 = obj.pop();
 * int param_3 = obj.top();
 * boolean param_4 = obj.empty();
 */
CATALOG
书籍阅读 算法 人工智能AI基础 机器学习-吴恩达 力扣 Java基础 numpy ollama工具 pandas spring6
FRIENDS