Cosmos 仓库栈(Stack)抽象数据类型全面解析:LIFO 原理、核心操作与多语言实现

原创2026-09-21 19:39:011,664 阅读
文章标签:教程示例工程

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 等进阶题目。

登录后查看全文
cosmos