一、前言
二、栈的数组实现
三、例题
四、习题
用自己的话说，栈更像是一个瓶子，有一个口、一个底，遵循着先进后出、后进先出的原则。
第一次接触栈是大一计算机基础课，当时学完，未果，觉得并没有什么用处。
第二次接触就是大三微机原理与接口课，依旧是没什么很大的感觉，感觉和一开始的接触变化不大，不过我当时确实是学懂了汇编语言，虽然现在忘光光的...
真正算是深入的接触就是看机械工业出版社《数据结构与算法——python语言实现》，栈一种数据类型，比如说撤销、返回等用到的其实都是栈的概念，也算是第一次了解了栈的实际作用。
先设计功能，设计最简单的四种功能：
功能代码实现压入栈push()弹出栈pop()求长度len()
我们采用列表的的方式存放栈，这里定义一个栈的类，初始化使其为一个空列表：
class ArrayStack: def __init__(self): """ Initialize the stack. """ self._data = []压入栈可以通过列表的拼接来实现，在list类中可以使用append()的方式进行拼接，这里注意，函数不需要返回值，这是直接对其局部变量进行修改：
def push(self, val): """ Use to push a element on the top of stack. """ self._data.append(val)同样的道理，弹出栈：
def pop(self): """ Use to pop the top element of stack. """ if self.is_empty(): raise Empty('Stack is empty!') return self._data.pop()在这之前，定义一个简单的查询列表是否为空的函数is_empty，既然要检验是否为空，就可以附加的再定义一个求长度的函数，这里用到了运算符重载。运算符重载简言就是对于我们自己写的类，如果想用常用函数或运算符进行直接计算是不可以的，比如说：
sample = ArrayStack() len(sample)程序就会退出并且报错：
Traceback (most recent call last):
File "\Python\test.py", line 39, in <module> len(sample)
TypeError: object of type 'ArrayStack' has no len()
这个时候想要解决，就要用到运算符重载来为他定义属于他独有的操作方式，例如len()的运算符重载为__len__，于是有：
def __len__(self): """ Return length of Stack. """ return len(self._data) def is_empty(self): """ Show if this stack empty or not. """ return len(self._data) == 0一个简单的列表栈就实现了。
1.括号匹配
一个算术表达式一定包含了多个括号，例如：
小括号：“(”和“)”中括号：“[”和“]”大括号：“{”和“}”其括号一定要相互前后匹配，例如小括号开一定要对应小括号闭，小括号开后面的中括号开一定要先进行中括号闭才能进行小括号开，但当我们一个算术表达式很长，我们要如何去检验这个是否正确呢，我们可以试想用栈的思维去解决：
观察我们的括号，其实括号是区分括号开（左括号）和括号闭（右括号）两种。当我们有一个栈，在遍历这个算术表达式的时候每读取到左括号时，进行一次压栈操作，将读取的左括号压入栈内；读到右括号时，进行弹出操作，将栈顶的左括号弹出，同时与当前的右括号进行比较（匹配），如果正确，则继续遍历....
具体代码如下：
def is_matched(expr): lefty = '([{' righty = ')]}' S = ArrayStack() for char in expr: if char in lefty: S.push(char) elif char in righty: if S.is_empty() or lefty.index(S.pop()) != righty.index(char): return False return True写完这段发现竟然有个测试用例是有问题的，即左括号没匹配完的情况，可我明明都在判断的时候进行了空的判断啊。
思考后发现原来是匹配过程没有问题的结束后，剩下的左括号也会默认为正确，只需要在结尾时再次判断其栈S是否匹配完即可：
def is_matched(expr): lefty = '([{' righty = ')]}' S = ArrayStack() for char in expr: if char in lefty: S.push(char) elif char in righty: if S.is_empty() or lefty.index(S.pop()) != righty.index(char): return False return S.is_empty()（我原本用了if，后来看书，书上是这样写的，写的真妙...）
2.HTML语言的正确错误检验：
同样的，HTML语言也有括号的检验过程，虽然HTML语言对于括号的判断非常简单（只有一种括号对，即<>），但想要更好的去判断就必须要判断括号内的标记。
同样的，在读取的过程中，我们可以用上面相同的思路。设一个中间变量temp，其类型是字符串，当我们遍历这个文章，读取到左括号<时，我们将后面的字符读进temp，当读到右括号>时结束读取，同时将temp压栈。一样的道理，当读到以斜杠/开头的标记时，读取到temp中，同时弹出、判断...往复直至结束。
思路是一样的，代码内容也相似，这里就不贴了。
按照书后的例题，给自己加加码，挑选了几道感兴趣的内容：
R-6.3 实现一个函数transfer(S,T)将栈S中所有元素倒置放入T。
C-6.16 修改栈的实现方法，加入一个参数maxlen，使其大小限制在maxlen中，若超出，则抛出一个异常。
C-6.18 实现R-6.3功能使其在原栈上更改输出。
