Cosmos 仓库 Stack 栈数据结构完全指南:LIFO 抽象、数组与链表实现及经典应用

原创2026-09-21 15:31:421,874 阅读
文章标签:教程示例工程

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_using_queue 则展示了跨结构的模拟实现,共同构成了从"接口定义 → 底层实现 → 跨结构模拟 → 实际应用"的完整学习链条。

小结

栈作为一个 LIFO 的抽象数据类型,以 Push、Pop、Peek、isEmpty 四个 O(1) 操作构成了无数算法的基石。通过 Cosmos 仓库的 栈专题目录,你既可以对照十余种语言掌握数组与链表两种实现方案的取舍,也可以跟随括号匹配、表达式转换、用队列模拟栈等真实代码,理解栈在编译器与算法设计中的核心地位。建议的进阶路径:先阅读 原理解读 建立概念,再精读 Java 数组实现 与 C++ 链表实现 对比两种方案,最后用 栈排序 等应用练习巩固,即可彻底掌握这一数据结构。

登录后查看全文
cosmos