用队列实现栈

发表于 更新于 分类于

算法-用队列实现栈

背景

  • 算法–用队列实现栈

  • 博主以代码随想录算法公开课进行学习

题目

  • 使用队列实现栈的下列操作：

    • push(x) – 元素 x 入栈
    • pop() – 移除栈顶元素
    • top() – 获取栈顶元素
    • empty() – 返回栈是否为空

    注意:

    • 你只能使用队列的基本操作-- 也就是 push to back, peek/pop from front, size, 和 is empty 这些操作是合法的。
    • 你所使用的语言也许不支持队列。 你可以使用 list 或者 deque（双端队列）来模拟一个队列 , 只要是标准的队列操作即可。
    • 你可以假设所有操作都是有效的（例如, 对一个空的栈不会调用 pop 或者 top 操作）

思路

  • 核心矛盾：队列是「先进先出（FIFO）」，栈是「后进先出（LIFO）」，需通过「队列元素倒腾」让「最后入队的元素」留在队首（模拟栈顶）；

代码

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
class MyStack {
    Queue<Integer> queue;

    public MyStack() {
       queue = new LinkedList<>();  
    }
    
    public void push(int x) {
        int size = queue.size();  // 记录入队前的元素个数
        queue.offer(x);
         // 把前面size个旧元素逐个出队，再入队到队尾，新元素留在队首（栈顶）
        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();
    }
}

总结

  • 面试可能考点：
    • 单队列 vs 双队列实现对比：
      • 双队列：入队 O (1)，出队 O (n)（倒腾 n-1 个元素）；
      • 单队列：入队 O (n)，出队 O (1)；
      • 本质：都是「空间换时间」，总时间复杂度一致，单队列代码更简洁；