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. 用栈实现队列

请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作(pushpoppeekempty):

实现 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
  • 最多调用 100pushpoppeekempty
  • 假设所有操作都是有效的 (例如,一个空的队列不会调用 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)的栈,并支持普通栈的全部四种操作(pushtoppopempty)。

实现 MyStack 类:

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

注意:

  • 你只能使用队列的标准操作 —— 也就是 push to backpeek/pop from frontsizeis 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
  • 最多调用100pushpoptopempty
  • 每次调用 poptop 都保证栈不为空

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


解法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();
 */