栈(Stack)是一种线性的数据存储结构，它具有如下特点：

　　（１）栈中的数据元素遵守先进后出（First In Last Out，FILO结构）的原则。

　　（２）限定只能在栈顶进行插入和删除操作。

　　如下图所示。

打个比方，栈就像一摞盘子，一个个的盘子摞成一叠，只能从最上面添加或拿走。最先放下的盘子入栈出栈在最底下，最后才能拿出，最后放下的盘子在最上面，最先被拿出。栈的常用操作如下：

　　（１）入栈：就是向栈中添加元素，只能从最上面添加，通常命名为push。

　　（２）出栈：也可称为弹栈，就是从栈中取出元素，只能从最上面取出，通常命名为pop。

　　（３）求栈的大小，返回栈中有多少个元素。

　　（４）判断栈是否为空，如果栈中无元素，返回True;如果栈中有元素，返回False。

　　栈这种数据结构，除了最顶的数据元素（也称节点）可见外，其它元素都要通过顶上元素的指针域才能访问。所以栈元素不能是基本类型数据，一定是对象。要创建对象，就要对象的模板——类。

　　栈的节点至少要有一个指针pre指向前一个节点，一般至少有一个节点属性值（如果没有属性值，这个节点就只是传递指针）。为了能够复用和拓展栈，栈主结构也采用类。

　　例题１：

　　（１）下图是节点类(stacknode.py)代码：

　　（２）下图是主结构类(stack.py)代码：

　　（３）下图是测试(stacktest.py)代码：

　　（４）下图是运行结果：

　　练习１：仿照例题１，设计一个栈能够同时入栈或出栈一对元素，然后编写测试代码测试。

　　例题２：用栈把十进制正整数转换成二进制数。

　　分析：十进制正整数转换为二进制正整数采用“除2取余，逆序排列”法，如下图所示。

　　具体做法：除数始终是2，用2整除十进制整数，可以得到一个商和余数；再用2去除商，又会得到一个商和余数，如此进行，直到商为0时为止，然后把先得到的余数作为二进制数的低位有效位，后得到的余数作为二进制数的高位有效位，依次排列起来。上图中，将十进制6转换成二进制数110。

　　程序代码：

　　运行结果：

　　练习题２：如果只用0, 1, 2, 3, 4, 5, 6, 7表示数，那是八进制；如果除了数字，还用大写或小写字母A, B, C, D, E, F分别表示10, 11, 12, 13, 14, 15，是十六进制，这两种进制也是计算机科学里常用的，在例题２中也加入这两种转换功能，输入一个十进制数转为三种进制字符串数并打印出来。

　　例题３：最小栈，就是当前栈顶元素的值始终是栈中元素的最小值。

　　分析：最小栈实现方式，每次入栈时进行判断，如果小于或等于栈顶元素，直接入栈；如果大于栈顶元素，栈先执行弹栈操作，然后把新值压入，最后把弹出的节点重新压回栈内，如图下图所示。

　　程序代码(minstack.py)：

　　（１）拓展Stack类，覆盖push方法；

　　（２）增加__add私有方法（连下划线）；

　　（３）增加printStack方法，可以观察加入过程。

　　运行结果：

　　练习题３：最大栈，就是当前栈顶元素的值始终是栈中元素的最大值。修改例题３代码，使之成为最大栈。

　　例题４：扩展栈（Stack），分别用递归和循环的方法，增加反转功能。

　　分析：栈的限制是人为的，只要把栈顶指针指向栈底节点，其它指针反向（节点指针指向变成被指向，原顶部节点指针指向None）。如下图所示。

　　递归代码：

　　循环代码：

　　运行结果：

　练习题４：把递归反转功能加到下面的代码中，然后完善if __name__ == "__main__":中的测试代码，运行测试。

参考资料：

１、《Python算法图解》何韬编著　清华大学出版社