栈：后进先出（LIFO）表。
特点：只允许在顶部进行存取操作的顺序表。
基本操作：
- push：入栈，即将元素压入栈顶
- pop：出栈，即将栈顶元素删除
- top：输出栈顶元素
应用场景：
- 平衡符号：编译器中用于检查符号是否成对出现，方法为做一个空栈，读取字符，如果字符是一个开放符号如“{”、“(”、“[”等，将其压入栈中。如果字符是一个封闭符号，如“}”、“)”、“]”，此时如果栈为空，说明有字符没有成对出现；否则将栈元素弹出，如果弹出的符号不是对应的开放符号，同样说明没有成对出现；如果字符读取完毕时栈不为空，也说明字符没有成对出现。
- 函数调用：函数在调用的时候，需要存储所有的重要信息，如变量名、返回地址等，这些信息就是通过栈来存储，然后控制转移到新的函数，当函数返回时从栈中取出存储的信息，继续从转移前的位置往下执行。递归函数对栈的使用开销极大，而且很容易导致栈溢出，可以通过栈操作来模拟递归过程。
栈的链表实现：
1 class Node(object): 2 def __init__(self, value=None, next=None): 3 self.value = value 4 self.next = next 5 6 7 class Stack(object): 8 def __init__(self, maxsize=8): 9 self._head = Node() # 表头，无实际意义10 self._top = None11 self.maxsize = maxsize12 self.length = 013 14 def pop(self):15 if self.length > 0:16 node = self._head.next17 self._head.next = node.next18 self.length -= 119 self._top = self._head.next20 else:21 raise Exception('Empty stack')22 23 def push(self, value):24 if self.length >= self.maxsize:25 raise Exception('Stack is full')26 node = Node(value)27 node.next = self._head.next28 self._head.next = node29 self.length += 130 self._top = self._head.next31 32 def top(self):33 if self.length > 0:34 return self._top.value35 else:36 raise Exception('Stack is empty')37 38 def __len__(self):39 return self.length 栈的数组实现：
1 from array import array 2 3 class Stack(object): 4 def __init__(self, maxsize=8): 5 self._array = array('i', range(maxsize)) 6 self.maxsize = maxsize 7 self.length = 0 8 self.index = -1 9 self._top = None10 11 def push(self, value):12 if self.length >= self.maxsize:13 raise Exception('Stack is full')14 self.index += 115 self._array[self.index] = value16 self.length += 117 self._top = value18 19 def pop(self):20 if self.length <= 0:21 raise Exception('Stack is empty')22 self.index -= 123 self.length -= 124 if self.index >= 0:25 self._top = self._array[self.index]26 else:27 self._top = None28 29 def top(self):30 return self._top31 32 def __len__(self):33 return self.length