数据结构（二）：栈

栈：后进先出（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 = none
11         self.maxsize = maxsize
12         self.length = 0
13 
14     def pop(self):
15         if self.length > 0:
16             node = self._head.next
17             self._head.next = node.next
18             self.length -= 1
19             self._top = self._head.next
20         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.next
28         self._head.next = node
29         self.length += 1
30         self._top = self._head.next
31 
32     def top(self):
33         if self.length > 0:
34             return self._top.value
35         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 = none
10 
11     def push(self, value):
12         if self.length >= self.maxsize:
13             raise exception('stack is full')
14         self.index += 1
15         self._array[self.index] = value
16         self.length += 1
17         self._top = value
18 
19     def pop(self):
20         if self.length <= 0:
21             raise exception('stack is empty')
22         self.index -= 1
23         self.length -= 1
24         if self.index >= 0:
25             self._top = self._array[self.index]
26         else:
27             self._top = none
28 
29     def top(self):
30         return self._top
31 
32     def __len__(self):
33         return self.length