当前位置：首页 > news >正文

每周算法思考：栈与队列

news 2025/8/10 12:12:11

1. 三合一（用一个数组实现三个栈）

题目描述

实现一个数据结构，使用一个数组同时实现三个栈，支持 push(stackNum, value)、pop(stackNum)、peek(stackNum)、isEmpty(stackNum) 操作。
stackNum 表示栈编号（0、1、2），每个栈的容量固定。

解法二：数组按段切分法

最简单高效的方法是固定分区法：将一个数组平均切成三个区域，每个区域维护独立的栈指针。

核心思想：数组长度 = stackSize * 3，第 i 个栈的起始索引为 i * stackSize，使用一个 sizes[] 数组记录每个栈当前元素数。
优点：实现简单，O(1) 操作。
缺点：栈之间不能共享剩余空间，可能浪费存储。

实现细节：

push(stackNum, value)：检查是否满栈，未满则将元素放入对应栈区的下一个空位置。
pop(stackNum)：检查是否空栈，非空则返回栈顶并减少计数。
peek(stackNum)：直接返回对应栈顶元素。
isEmpty(stackNum)：判断 sizes[stackNum] == 0。

代码实现（Java 示例）：

class TripleInOne {private int[] stackData;  // 存储三个栈数据private int stackSize;    // 每个栈容量private int[] sizes;      // 每个栈当前元素数量public TripleInOne(int stackSize) {this.stackSize = stackSize;stackData = new int[stackSize * 3];sizes = new int[3]; // 初始化三个栈的大小}public void push(int stackNum, int value) {if (sizes[stackNum] == stackSize) return; // 满栈int index = getTopIndex(stackNum) + 1;stackData[index] = value;sizes[stackNum]++;}public int pop(int stackNum) {if (isEmpty(stackNum)) return -1;int topIndex = getTopIndex(stackNum);int value = stackData[topIndex];sizes[stackNum]--;return value;}public int peek(int stackNum) {if (isEmpty(stackNum)) return -1;return stackData[getTopIndex(stackNum)];}public boolean isEmpty(int stackNum) {return sizes[stackNum] == 0;}// 获取栈顶索引private int getTopIndex(int stackNum) {int offset = stackNum * stackSize;int size = sizes[stackNum];return offset + size - 1;}
}

复杂度分析：

时间复杂度：O(1)（所有操作）
空间复杂度：O(stackSize × 3)（固定数组存储）

解法二：动态分区 + 环形数组 + 扩容搬移

核心思想：
- 数组视作环形结构（环状数组），头尾相连，避免固定边界限制。
- 每个栈维护开始索引、容量和当前大小。
- push 时，如果当前栈满，尝试扩容（向其他栈“借用”空间），通过搬移相邻栈的元素调整空间。
- 搬移操作基于环形数组顺序，保证所有栈的数据顺序连续。
关键点：
- 使用链式或结构体保存每个栈的边界信息。
- 搬移元素时，必须注意环绕情况和索引计算。
- 复杂度较固定分区法高，实现难度也大，但能更充分利用空间。

伪代码逻辑大致如下：

push(stackNum, val):if 栈满:扩容(stackNum)插入元素，更新栈大小扩容(stackNum):计算需要扩容的空间尝试搬移相邻栈元素以腾出空间更新所有栈的起始位置和容量

总结

固定分区法实现简单、性能 O(1)，适合容量已知且均匀分配的场景；如果需要动态共享空间，可以使用灵活分区法（如循环队列 + 栈指针）来提升利用率，但实现更复杂。

2. 栈的最小值

题目描述

设计一个栈，除了支持常规的 push 和 pop 操作，还支持一个 min 函数，该函数能在 O(1) 时间内返回栈中的最小元素。要求所有操作的时间复杂度均为 O(1)。

输入：一系列 push、pop 和 min 操作
输出：min 操作返回当前栈中的最小值

解题思路

解法一：辅助栈存储当前最小值（推荐）

维护两个栈：

主栈 stack 用于存储所有元素
辅助栈 minStack 用于存储当前栈中的最小元素，栈顶始终保存当前最小值

关键逻辑：
每次 push 新元素时，将该元素与 minStack 栈顶的最小值比较，如果新元素更小或相等，则将它也压入 minStack。
每次 pop 时，如果弹出的元素等于 minStack 栈顶元素，也同步弹出 minStack。

这样，minStack 的栈顶元素就是当前主栈的最小值，实现 min 操作为 O(1)。

代码实现（Java 示例）

import java.util.Stack;public class MinStack {private Stack<Integer> stack;private Stack<Integer> minStack;public MinStack() {stack = new Stack<>();minStack = new Stack<>();}public void push(int x) {stack.push(x);if (minStack.isEmpty() || x <= minStack.peek()) {minStack.push(x);}}public void pop() {if (stack.isEmpty()) return;int top = stack.pop();if (top == minStack.peek()) {minStack.pop();}}public int top() {if (stack.isEmpty()) throw new RuntimeException("Stack is empty");return stack.peek();}public int min() {if (minStack.isEmpty()) throw new RuntimeException("Stack is empty");return minStack.peek();}
}