LeetCode 232. 用栈实现队列

Categories:

Tags:

题目描述
思路分析
1. 解法一：双栈法（推荐）
相似题目

题目描述

✅ 232. 用栈实现队列

思路分析

解法一：双栈法（推荐）

核心思路：

用两个栈模拟队列的 FIFO 特性：

inStack（输入栈）：专门负责 push 操作，所有新元素压入 inStack

outStack（输出栈）：专门负责 pop/peek 操作，当 outStack 为空时，将 inStack 全部元素转移过来

关键推导：

栈是 LIFO，两次反转 = FIFO

转移操作保持了元素在 outStack 中的队列顺序（inStack 栈顶 → outStack 栈底）

惰性转移：只有 outStack 为空时才转移，均摊每个元素仅被移动一次

均摊复杂度：每个元素先入 inStack 再出 inStack 入 outStack 再出 outStack，共 2 次进出，均摊 O(1)。

复杂度分析：

时间复杂度：push O(1)；pop/peek 均摊 O(1)，最坏 O(n)（触发批量转移）

空间复杂度：O(n)，两栈共存储 n 个元素

class MyQueue {
    private Deque<Integer> inStack;
    private Deque<Integer> outStack;

    public MyQueue() {
        inStack = new ArrayDeque<>();
        outStack = new ArrayDeque<>();
    }

    public void push(int x) {
        inStack.push(x);
    }

    public int pop() {
        // 仅当输出栈为空时，才将输入栈全部转移
        move();
        return outStack.pop();
    }

    public int peek() {
        move();
        return outStack.peek();
    }

    public boolean empty() {
        return inStack.isEmpty() && outStack.isEmpty();
    }

    private void move() {
        if (outStack.isEmpty()) {
            while (!inStack.isEmpty()) {
                outStack.push(inStack.pop());
            }
        }
    }
}

type MyQueue struct {
	inStack  []int
	outStack []int
}

func Constructor() MyQueue {
	return MyQueue{}
}

func (q *MyQueue) Push(x int) {
	q.inStack = append(q.inStack, x)
}

func (q *MyQueue) Pop() int {
	// 仅当输出栈为空时，才将输入栈全部转移
	if len(q.outStack) == 0 {
		for len(q.inStack) > 0 {
			n := len(q.inStack)
			q.outStack = append(q.outStack, q.inStack[n-1])
			q.inStack = q.inStack[:n-1]
		}
	}
	n := len(q.outStack)
	val := q.outStack[n-1]
	q.outStack = q.outStack[:n-1]
	return val
}

func (q *MyQueue) Peek() int {
	if len(q.outStack) == 0 {
		for len(q.inStack) > 0 {
			n := len(q.inStack)
			q.outStack = append(q.outStack, q.inStack[n-1])
			q.inStack = q.inStack[:n-1]
		}
	}
	return q.outStack[len(q.outStack)-1]
}

func (q *MyQueue) Empty() bool {
	return len(q.inStack) == 0 && len(q.outStack) == 0
}

相似题目

题目	难度	考察点
225. 用队列实现栈	简单	用队列模拟栈
155. 最小栈	中等	辅助栈记录最小值
716. 最大栈	困难	辅助栈记录最大值
641. 设计循环双端队列	中等	队列结构设计
622. 设计循环队列	中等	循环队列实现
20. 有效的括号	简单	栈的典型应用

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2026/06263683