Cosmos 仓库栈(Stack)抽象数据类型全面解析:LIFO 原理、核心操作与多语言实现
Cosmos 仓库栈(Stack)抽象数据类型全面解析:LIFO 原理、核心操作与多语言实现
栈(Stack)是一种遵循后进先出(LIFO, Last-In-First-Out)原则的抽象数据类型(ADT),是计算机科学中最基础、应用最广泛的数据结构之一。本文以 Cosmos 开源算法仓库中的 栈文档 为核心,结合仓库内十余种语言的源码实现,系统讲解栈的定义、四大核心操作、时间复杂度、数组与链表两种底层实现方式,并延伸介绍其在表达式求值、括号匹配等场景中的典型应用。读完本文,你将掌握栈的完整原理,并能对照多语言源码独立实现与使用栈。
栈的本质:抽象数据类型(ADT)与 LIFO 规则
栈首先是一种抽象数据类型——它不规定底层必须用某种具体结构,而是定义了一组操作契约:数据只能从同一端(称为栈顶 top)进出,从而保证后进先出的顺序。
原文用两个经典比喻帮助理解这一特性:
- 汉诺塔:最先放入塔底的对象,必须等所有叠在其上的对象全部移走之后才能被取出;
- 餐厅叠放的餐盘:最底下的盘子无法直接取用,必须先把上方所有盘子一一拿走。
这两个比喻精确刻画了 LIFO 的本质:访问顺序与插入顺序严格相反。在 Cosmos 仓库中,这一 ADT 定义被记录在 abstract_stack/README.md,而具体实现则分布在 stack 目录 下的 17 个源文件中,覆盖 C、C++、Java、Python、Go、Rust、Swift、Ruby、JavaScript、PHP、C#、Erlang、Elixir、Dart 等主流语言。
核心操作:Push / Pop / Peek / isEmpty
抽象栈契约规定四类核心操作,原文档 中给出了明确语义:
| 操作 | 行为 | 返回值 |
|---|---|---|
Push() |
将元素压入栈顶 | 无 |
Pop() |
移除并返回栈顶元素 | 被移除的元素 |
Peek() |
只查看栈顶元素,不修改栈 | 栈顶元素 |
isEmpty() |
判断栈是否为空 | true / false |
从仓库源码看,各语言实现与契约完全对应。以 Python 的数组实现 stack.py 为例:
class Stack:
def __init__(self):
self.stack_arr = [] # 用 Python 列表模拟数组
def push(self, data):
self.stack_arr.append(data) # 压入栈顶
def is_empty(self):
return len(self.stack_arr) == 0
def pop(self):
assert len(self.stack_arr) > 0, "The stack is empty!"
return self.stack_arr.pop() # 弹出栈顶
def peek(self):
assert len(self.stack_arr) > 0, "The stack is empty!"
return self.stack_arr[-1] # 仅查看栈顶
该实现还体现了健壮性设计:pop() 与 peek() 对空栈执行时抛出断言异常,避免静默产生错误结果。
Go 版本 stack.go 则展示了另一种编程风格——以切片为底层的函数式 API:
type Stack []int
func (s *Stack) Push(v int) Stack { return append(*s, v) }
func (s *Stack) Pop() Stack {
length := len(*s)
if length != 0 {
return (*s)[:length-1]
}
return *s
}
func (s *Stack) Top() int { return (*s)[len(*s)-1] }
func (s *Stack) Empty() bool { return len(*s) == 0 }
Go 版额外提供了 Top()(等价于 Peek)并处理了空栈 Pop 的边界情况。
时间复杂度:所有核心操作均为 O(1)
原文档 明确指出:所有函数的时间复杂度均为 O(1)。
这一点可以从两种底层实现中直接验证:
- 数组实现:
Push在数组尾部追加、Pop在尾部移除,只需通过top索引定位,无需移动其他元素。参考 stack.c 中的push与pop:void push(struct Stack* stack, int item) { assert(!is_full(stack)); stack->array[++stack->top] = item; // 常数次操作 } int pop(struct Stack* stack) { assert(!is_empty(stack)); return (stack->array[stack->top--]); // 常数次操作 } - 链表实现:入栈只需在头节点前插入新节点(O(1)),出栈只需移动头指针并删除原头节点(O(1))。参考 stack.cpp 的链表节点版:
void push(T n) { Node<T>* ptr = new Node<T>; ptr->n = n; ptr->next = top; // 新节点指向旧栈顶 top = ptr; // 更新栈顶 } T pop() { if (top == nullptr) return INT_MIN; Node<T>* ptr = top; T n = ptr->n; top = top->next; // 栈顶下移 delete ptr; return n; }
注意空间开销的差异:数组实现可能存在容量上限(参考 stack.c 中 create_stack(capacity) 与 is_full 的溢出检查,以及 stack.java 中 maxSize 与 isFull() 的满栈保护);链表实现则按需动态分配内存,不存在固定容量问题,但每个元素额外占用一个指针域的空间。
两种底层实现:数组 vs 链表
原文档指出,实现栈可以使用数组或链表。仓库中两种方案均有完整源码:
数组实现
- stack.c:C 语言数组实现,含
create_stack/delete_stack的内存管理,is_full/is_empty双边界检查,push/pop使用断言防溢出与下溢; - stack.java:Java 泛型实现
Stack<T>,基于ArrayList,提供isFull()、makeEmpty()等附加方法,空栈pop/peek抛出IndexOutOfBoundsException; - stack.py:Python 列表实现;
- stack_using_array.py:过程式风格的 Python 版本,用全局列表 + 函数实现,并在空栈弹出时返回
"STACK UNDERFLOW"提示。
链表实现
- stack.cpp:C++ 模板类
Stack<T>,以Node<T>单向链表为底层,含析构函数逐节点释放内存,并附带display()交互菜单(Push / Pop / Display / Exit); - stack_using_linked_list.py:Python 链表实现,定义
node与stack两个类,insertnode头插法入栈、deletenode头删法出栈,并打印链表形态a->b->c->NULL。
如何选择
| 维度 | 数组实现 | 链表实现 |
|---|---|---|
| 容量 | 固定(可扩容策略需自行实现) | 动态增长 |
| 内存 | 连续、紧凑、缓存友好 | 每个节点额外存指针 |
| 栈顶操作 | O(1) | O(1) |
| 溢出风险 | 有(满栈 Push) | 无(内存足够时) |
栈的应用场景与仓库实例
栈的 LIFO 特性使其天然适合"回溯""撤销""嵌套配对"类问题。Cosmos 仓库的 stack 目录 下收录了大量直接基于栈的实际应用:
- 表达式转换与求值:
infix_to_postfix(中缀转后缀)、infix_to_prefix(中缀转前缀)、postfix_evaluation(后缀求值)、postfix_to_prefix、prefix_to_postfix——栈用于保存运算符并正确处理优先级与括号; - 括号匹配:
balanced_expression——利用栈判断括号序列是否配对合法; - 栈的变换:
reverse_stack(栈反转)、sort_stack(栈排序)、reverse_array_using_stack(借助栈反转数组); - 算法结合:
Quick_sort_usingSack(用栈模拟快速排序的非递归版本)、stack_using_queue(用队列实现栈的趣味结构题)。
这些目录展示了栈不仅是教科书概念,更是表达式解析、编译器语法分析、函数调用栈、浏览器前进后退等真实系统的核心组件。例如后缀表达式的求值流程就是典型的"遇操作数入栈、遇运算符弹出两个操作数计算后压回"的栈操作序列。
小结
栈作为经典的抽象数据类型,其价值在于用最简单的位置约束(只能操作栈顶)换来 O(1) 的插入、删除与查看效率。本文结合 原文档 与仓库内 stack 目录下的多语言源码,完整覆盖了栈的 LIFO 原理、四大核心操作、时间复杂度证明、数组/链表双实现对比及其典型应用。如果你想亲手实践,可以运行 stack.c(数组版交互程序)或 stack.cpp(链表版菜单程序),再进一步挑战 infix_to_postfix 与 balanced_expression 等进阶题目。