Python 数据结构入门 - 栈（Stack）

什么是栈

只允许在一端进行插入或删除数据元素的有限序列。

栈顶：进行插入和删除的那一端；栈底：栈顶的另一端。

栈的特点

数据元素遵循后进先出原则：LIFO (last in, first out)。

栈的应用

除了能够解决很多算法问题之外，在大多数的编程语言中，都会使用栈来记录程序的运行状态。

动手试一试

（提示：点击交互式代码框右上角绿色三角按钮可运行代码）

下面是一个简单的栈实现，先不要关心实现原理，亲自试一试栈的各种操作吧

1. 创建一个栈，并添加几个元素

2. 栈顶元素出栈，并打印整个栈

3. 向栈 a 中插入元素 p q y x z，并打印整个栈

5. 删除两次栈顶元素，并打印整个栈

栈的经典案例

1. 括号匹配

假如表达式中允许包含三中括号 ()、[]、{}，其嵌套顺序是任意的，例如：

正确的格式：{()[()]},[{({})}]

错误的格式：[(]),[()),(()}

使用上面的 Stack 类编写一个函数，判断一个表达式字符串，括号匹配是否正确

2. 后缀表达式求值

计算一个表达式时，编译器通常使用后缀表达式，这种表达式不需要括号，便于程序进行处理。

3. 背包问题

有一个背包能装 10 kg 的物品，现在有 6 件物品分别为：

编写找出所有能将背包装满的解，如物品1+物品5。