LeetCode 补充题 121. 用数组实现定长栈
题目描述
:::fold-green 相关原题
牛客原题： ✅ 【模板】栈
牛客原题没有满栈限制，支持 push、pop、top，空栈读取或出栈输出 error，入栈不输出。本文额外规定固定容量及满栈返回值；用于牛客输入时，可按操作总数分配数组，将 top 对应到 peek，并按题面转换输出。
:::
请使用原生整数数组实现一个容量固定为
capacity的栈，支持以下操作：
push(value)：将value压入栈顶。成功返回true；栈已满时不修改栈，返回false。pop()：删除并返回栈顶元素。peek()：返回栈顶元素，不修改栈。isEmpty()：返回栈是否为空。空栈调用
pop()或peek()时，Java 返回null，Go 返回失败标志(value, false)。
示例 1：
输入：
capacity = 2, 操作 = [push(4), push(6), push(8), pop(), peek()]
输出：[true,true,false,6,4]
解释： 第三次入栈时容量已满；出栈得到最后成功入栈的 6，随后栈顶为 4。
提示：
-
capacity≥0，容量固定。 - 满栈
push返回false。 - 空栈读取或出栈时，Java 返回
null，Go 返回失败标志。
题意分析
栈只在一端插入和删除，数组无需搬移已有元素。用一个有效长度标记栈顶边界，就能在固定容量内完成后进先出操作；容量满和栈为空时必须按题面返回失败。
解法：数组与有效长度模拟固定栈
核心思路
[!blue]
维护不变量
0 <= size <= capacity，有效元素为values[0..size-1]。size指向下一次入栈的空位，栈顶是size - 1，两者不能混用。入栈先判满，再写入
values[size]并递增；出栈先判空，再递减size，读取此时下标处的旧栈顶。peek只读取size - 1，不改变有效长度；isEmpty检查size == 0。弹出后数组中遗留的整数不属于有效区间，无需搬移或清零。失败操作必须保持
size不变，容量为 0 时任何入栈都失败。空栈返回标记与元素值分离，因此整数 0 仍可正常存入。
解题步骤
- size 既是有效元素数，也是下一次写入位置。
- push 先判满，再写入 values[size] 并增加 size。
- pop 先判空，再减少 size 后读取；peek 读取 size-1 但不改变状态。
代码实现
class ArrayStack {
private final int[] values;
private int size;
ArrayStack(int capacity) {
values = new int[capacity];
}
public boolean push(int value) {
if (size == values.length) {
return false;
}
values[size++] = value;
return true;
}
public Integer pop() {
return size == 0 ? null : values[--size];
}
public Integer peek() {
return size == 0 ? null : values[size - 1];
}
public boolean isEmpty() {
return size == 0;
}
}
type ArrayStack struct {
values []int
size int
}
func NewArrayStack(capacity int) *ArrayStack {
return &ArrayStack{values: make([]int, capacity)}
}
func (s *ArrayStack) Push(value int) bool {
if s.size == len(s.values) {
return false
}
s.values[s.size] = value
s.size++
return true
}
func (s *ArrayStack) Pop() (int, bool) {
if s.size == 0 {
return 0, false
}
s.size--
return s.values[s.size], true
}
func (s *ArrayStack) Peek() (int, bool) {
if s.size == 0 {
return 0, false
}
return s.values[s.size-1], true
}
func (s *ArrayStack) IsEmpty() bool {
return s.size == 0
}
复杂度分析
- 时间复杂度：各操作时间 $O(1)$。
- 空间复杂度：预分配空间 $O(capacity)$。
关键点总结
[!green]
固定容量将扩容搬移排除在操作流程外；空栈与满栈行为是接口约定的一部分。
易错点总结
[!yellow]
size指向下一个空位，栈顶在size-1；这里明确采用定长容量，扩容版本可改为动态数组。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 补充题 142. 实现动态整数数组 | 中等 | 固定容量不扩容，因此 push 最坏常数；动态数组追加只保证均摊常数，扩容当次需要复制。 |
| 155. 最小栈 | 中等 | 在基础栈操作上增加每层最小值状态，即可扩展为最小栈。 |