本文档涵盖了存储库中基础线性数据结构的实现和应用，特别是栈及其算法应用。重点关注后进先出（LIFO）和先进先出（FIFO）的访问模式，以及它们在表达式解析、求值和验证算法中的应用。
有关基于树的层次结构，请参阅 树和基于树的结构。有关基于堆的优先级结构，请参阅 堆和优先级队列。有关更复杂的非线性结构，请参阅 高级数据结构。
存储库提供了完整的通用栈实现，具有溢出/欠流保护和全面的操作。
来源： data_structures/stacks/stack.py1-216
Stack 类提供基本 LIFO 操作，并附带安全机制
| 操作 | 方法 | 时间复杂度 | 描述 |
|---|---|---|---|
| 推送 | push(data) | O(1) | 将元素添加到顶部，如果已满则引发 StackOverflowError |
| 弹栈（Pop） | pop() | O(1) | 移除并返回顶部元素，如果为空则引发 StackUnderflowError |
| Peek | peek() | O(1) | 不移除地返回顶部元素 |
| 大小检查 | size() | O(1) | 返回当前元素数量 |
| 判空 | is_empty() | O(1) | 如果栈不包含任何元素，则返回 True |
| 判满 | is_full() | O(1) | 如果栈已达到容量限制，则返回 True |
| 成员资格检查 | __contains__() | O(n) | 检查元素是否存在于栈中 |
来源： data_structures/stacks/stack.py35-158
实现包括强大的错误处理和边界检查
来源： data_structures/stacks/stack.py35-94
存储库演示了栈在解析和表达式求值中的几个经典应用。
来源： data_structures/stacks/balanced_parentheses.py1-39 data_structures/stacks/infix_to_postfix_conversion.py1-114 data_structures/stacks/dijkstras_two_stack_algorithm.py1-85
balanced_parentheses 函数演示了栈在语法验证中的使用
来源： data_structures/stacks/balanced_parentheses.py4-26
infix_to_postfix 函数实现了 Shunting Yard 算法，使用了运算符优先级和结合性
| 运算符 | 优先级 | 结合性 | 示例 |
|---|---|---|---|
^ | 3 | 从右到左 | 2^3^2 → 2 3 2 ^ ^ |
*, / | 2 | 从左到右 | a*b/c → a b * c / |
+, - | 1 | 从左到右 | a+b-c → a b + c - |
来源： data_structures/stacks/infix_to_postfix_conversion.py12-25 data_structures/stacks/infix_to_postfix_conversion.py45-103
表达式求值器使用两个栈来处理完全括号化的表达式
来源： data_structures/stacks/dijkstras_two_stack_algorithm.py40-79
尽管页面标题中包含队列，但存储库目前缺少专门的队列实现。这为遵循栈实现建立的模式进行贡献提供了一个机会。
栈和队列都遵循类似的线性数据访问模式，但具有不同的排序语义。
| 结构 | 访问模式 | 主要操作 | 用例 |
|---|---|---|---|
| 栈 | LIFO (后进先出) | push(), pop(), peek() | 表达式解析、函数调用、撤销操作 |
| 队列 | FIFO (先进先出) | enqueue(), dequeue(), front() | 任务调度、广度优先搜索、缓冲 |
来源： data_structures/stacks/stack.py35-94
基于栈的实现是存储库中更复杂算法的构建模块。
来源： data_structures/stacks/balanced_parentheses.py1-39 data_structures/stacks/infix_to_postfix_conversion.py1-114 data_structures/stacks/dijkstras_two_stack_algorithm.py1-85