Cosmos 仓库 Stack 栈数据结构完全指南:LIFO 抽象、数组与链表实现及经典应用
Cosmos 仓库 Stack 栈数据结构完全指南:LIFO 抽象、数组与链表实现及经典应用
栈(Stack)是计算机科学中最基础也最重要的抽象数据类型(ADT)之一,其"后进先出"(LIFO)的存取顺序贯穿于函数调用、表达式求值、括号匹配与撤销操作等几乎所有软件场景。本文以 OpenGenus Cosmos 仓库中的 栈专题目录 为骨架,完整讲解栈的核心操作、O(1) 时间复杂度、数组与链表两种底层实现方案,并结合仓库内十余种语言的真实源码与经典应用(括号匹配、中缀转后缀、用队列实现栈等),帮助你从概念到源码一次性吃透栈。
栈是什么:一种后进先出(LIFO)的抽象数据类型
在计算机科学中,栈是一种抽象数据类型(Abstract Data Type, ADT),它只暴露一组定义良好的操作接口,而隐藏内部数据的存储细节。栈的核心约束是存取顺序:后放入的元素先被取出,即 Last-In-First-Out(LIFO)。
正如 仓库中的栈说明文档 所描述的,栈的行为与两个日常场景完全一致:
- 汉诺塔(Tower of Hanoi):最先放入底座的圆盘,必须等它上方所有圆盘都被移走之后才能移动——这与"先压入栈底、最后弹出"的语义如出一辙。
- 食堂里的盘子堆:最底下的盘子无法直接取用,必须先把上面一层层盘子拿走——这就是 LIFO 最直观的物理模型。
因为栈只允许在**同一端(栈顶 top)**进行插入和删除,所以它是一种受限的线性结构:数据的物理存放可以是连续的(数组)或离散的(链表),但逻辑上的访问入口始终只有栈顶一个。
栈的四大核心操作
原文档定义了栈必须提供的四个基本操作,这是所有语言实现共同遵守的最小接口约定:
| 操作 | 语义 | 行为说明 |
|---|---|---|
Push() |
入栈 | 将一个元素压入栈顶 |
Pop() |
出栈 | 移除并返回栈顶元素 |
Peek() |
查看栈顶 | 返回栈顶元素的值,但不移除它 |
isEmpty() |
判空 | 若栈内无任何元素则返回 true |
其中 Peek() 与 Pop() 的关键区别在于是否有副作用:Peek() 只读不删,Pop() 既读又删。理解这一区别对正确编写使用栈的算法至关重要。
值得一提的是,仓库的抽象接口设计对这套操作集合进行了更严格的规范化。在 抽象栈接口 中,IStack 通过 C++ 纯虚函数(= 0)定义了栈的完整契约,除了 push、pop、peek、isEmpty 外还扩展了 toString()(返回栈的字符串表示)与虚析构函数,任何实现类都必须提供这些能力:
template <typename T>
class IStack {
public:
virtual ~IStack() {};
virtual void push(const T& element) = 0; // 入栈
virtual T pop() = 0; // 出栈
virtual T peek() const = 0; // 查看栈顶(只读)
virtual bool isEmpty() const = 0; // 判空
virtual std::string toString() const = 0; // 字符串化
};
接口先行、实现分离,这正是 ADT 思想的工程化落地:使用方只需面向 IStack 编程,无需关心底层是数组还是链表。
时间复杂度:全部核心操作均为 O(1)
原文档明确指出:栈的所有核心函数时间复杂度都是 O(1)。这是栈区别于许多线性结构(如需要移位或查找的结构)的最大优势:
Push():无论基于数组(在末尾追加)还是链表(在头节点插入),都只需常数次操作;Pop()/Peek():直接访问栈顶,无需遍历;isEmpty():仅需比较一个标记(栈顶指针或链表头指针)是否为空。
常数时间的入出栈特性,使栈成为表达式求值、深度优先遍历、回溯算法等场景中最高效的临时存储结构。
两种经典实现:数组栈与链表栈
原文档指出:"要实现一个栈,可以使用数组(array)或链表(linked list)"。仓库在 栈实现目录 下用十余种语言(C、C++、C#、Dart、Elixir、Erlang、Go、Java、JavaScript、PHP、Python、Ruby、Rust、Swift)分别给出了两种底层的实现,下面以仓库真实源码为例剖析两种方案的差异。
数组实现:连续内存 + 栈顶游标
数组栈借助"栈顶下标"(top index)管理元素,出栈入栈都只发生在数组的一端。仓库的 Java 数组实现 是一个完整范例,其核心要点包括:
- 用
top指针标记栈顶位置,初始为-1表示空栈; push时先检查isFull()防止上溢(overflow),再将top自增后写入;pop时先检查isEmpty()防止下溢(underflow),再返回top指向的元素并递减游标;- 额外提供
isFull()与makeEmpty()(将top重置为 -1,后续push会覆盖旧值)等实用方法。
public void push(T value){
if(!isFull()){
top++;
if(stackArray.size() <= top)
stackArray.add(top, value);
else
stackArray.set(top, value);
}else{
System.out.println("The stack is full, can't insert value");
}
}
public T pop(){
if(!isEmpty()){
return stackArray.get(top--);
}else{
throw new IndexOutOfBoundsException();
}
}
public boolean isEmpty(){
return(top == -1);
}
public boolean isFull(){
return(top+1 == maxSize);
}
仓库对应的 Python 数组实现 则更简洁——直接利用 Python 内置 list 的 append 与索引访问实现 push、pop、isEmpty,并以 STACK UNDERFLOW 提示处理下溢:
stack=[]
def push(item):
stack.append(item)
def pop():
if isEmpty(stack):
return("STACK UNDERFLOW")
else:
itempopped=stack[-1]
stack.pop
display()
return int(itempopped)
def isEmpty(stack):
return stack==[]
数组栈的优点:缓存友好、访问快速(元素在内存中连续存放),且没有指针开销;缺点:容量固定,扩容时需要整体搬迁(实际工程中多采用动态扩容的均摊 O(1))。
链表实现:动态节点 + 头插头删
链表栈的每个元素是独立节点,通过指针串联,栈顶即链表头。仓库的 C++ 模板链表实现 用 Node<T> 结构体加 top 指针实现,push 采用"头插法",pop 删除头节点,析构函数逐节点释放内存防止泄漏:
template <class T> void Stack<T>::push(T n)
{
Node<T>* ptr = new Node<T>;
ptr->n = n;
ptr->next = top; // 新节点指向旧栈顶
top = ptr; // 新节点成为栈顶
}
template <class T> T Stack<T>::pop()
{
if (top == nullptr)
return INT_MIN; // 空栈标记
Node<T>* ptr = top;
T n = ptr->n;
top = top->next; // 栈顶下移
delete ptr;
return n;
}
仓库中的 Python 链表实现 采用同样的头插/头删思路:insertnode 创建新节点并挂在链表头部,deletenode 移除头节点,display 沿指针链打印到 NULL 结束。
链表栈的优点:容量动态、无上溢(受堆内存限制);缺点:每个节点有指针额外开销,且节点在内存中离散分布,缓存命中率低于数组栈。
仓库中相关的链表实现细节可继续阅读 单链表实现 与 Linked_List 系列。
进阶:用两个队列实现栈
栈和队列是一对互补的受限线性结构,它们可以互相模拟。仓库的 用队列实现栈 演示了如何用两个队列(main_q 与 auxiliary_q)构造一个栈:
push(val):先把元素放入辅助队列,再把主队列全部元素依次搬入辅助队列,最后swap两个队列,使新元素始终处于队首(即"栈顶");pop()/top():直接操作主队列队首即可;- 该实现把计算负担集中在
push(O(n)),换取pop/top的 O(1)。
源码文件末尾还内嵌了基于 assert 的自测用例(assert(s.size()==3)、assert(s.top()==3) 等),完整验证了 push 3 个元素、连续 pop、再次 push 后栈顶变化与 size 的每一步正确性——这为读者提供了一个"栈行为可验证"的最小测试模板,也体现了 Cosmos 仓库"代码即文档、测试随附"的风格。
栈的经典应用:仓库中的实战案例
栈绝非仅停留在教科书层面,仓库的 栈目录 下收集了大量直接使用栈解决真实问题的实现,可作为算法实战参考:
| 应用 | 仓库路径 | 解决的问题 |
|---|---|---|
| 括号匹配 | balanced_expression(C/C++/Java/Python) | 判断 {}、[]、() 是否成对闭合 |
| 中缀转后缀 | infix_to_postfix | 将人类习惯的中缀表达式转为机器易求值的后缀表达式 |
| 中缀转前缀 | infix_to_prefix | 中缀表达式转前缀(波兰式) |
| 后缀表达式求值 | postfix_evaluation | 直接计算后缀表达式结果 |
| 后缀转前缀 / 前缀转后缀 | postfix_to_prefix、prefix_to_postfix | 表达式表示法之间的互转 |
| 用栈反转数组 / 反转栈 | reverse_array_using_stack、reverse_stack | 借助栈天然的反序特性 |
| 栈排序 | sort_stack、Quick_sort_usingSack | 仅用栈操作完成排序 |
以括号匹配为例,balanced_expression.cpp 的算法逻辑清晰展示了栈的核心价值:遇到左括号 (、[、{ 就 push 入栈;遇到右括号则与栈顶元素比对,若配对成功则 pop,否则判定非法;最终字符串遍历完毕时,栈恰好为空才是平衡表达式。这一"后遇到的左括号先被匹配"的特性,正是 LIFO 语义的直接体现,也是编译器语法分析、IDE 括号高亮等功能的底层原理。
多语言实现一览:从 C 到 Rust 的完整覆盖
Cosmos 仓库以"贡献者驱动、多语言全覆盖"著称,栈的 多语言实现目录 就是一个缩影,它让读者可以在同一语义下横向对比不同语言的写法:
- 系统级语言:stack.c(C)、stack.cpp(C++ 模板)、stack.rs(Rust)、stack.go(Go)
- JVM 生态:stack.java(Java 泛型)、stack.scala(Scala,位于同目录)
- 脚本语言:stack.py、stack_using_array.py、stack_using_linked_list.py(Python)、stack.js(JavaScript)、stack.rb(Ruby)、stack.php(PHP)
- 函数式与并发风格:stack.ex(Elixir)、stack.erl(Erlang)、stack.swift(Swift)、stack_in_dart.dart(Dart)
此外,抽象栈目录 还提供了"接口 + 数组实现"分离的工程化示例,stack_using_queue 则展示了跨结构的模拟实现,共同构成了从"接口定义 → 底层实现 → 跨结构模拟 → 实际应用"的完整学习链条。
小结
栈作为一个 LIFO 的抽象数据类型,以 Push、Pop、Peek、isEmpty 四个 O(1) 操作构成了无数算法的基石。通过 Cosmos 仓库的 栈专题目录,你既可以对照十余种语言掌握数组与链表两种实现方案的取舍,也可以跟随括号匹配、表达式转换、用队列模拟栈等真实代码,理解栈在编译器与算法设计中的核心地位。建议的进阶路径:先阅读 原理解读 建立概念,再精读 Java 数组实现 与 C++ 链表实现 对比两种方案,最后用 栈排序 等应用练习巩固,即可彻底掌握这一数据结构。