1 #!/usr/bin/env python
2 # -*- coding:utf-8 -*-
3
4
5 class StackUnderflow(ValueError):
6 pass
7
8 #链表节点
9 class Node(object):
10 def __init__(self, elem, next_ = None):
11 self.elem = elem
12 self.next = next_
13
14 #顺序表实现栈
15 class SStack(object):
16 def __init__(self):
17 self._elems = []
18
19 def is_empty(self):
20 return self._elems == []
21
22 def top(self):
23 if self.is_empty():
24 raise StackUnderflow
25 return self._elems[-1]
26
27 def push(self, elem):
28 self._elems.append(elem)
29
30 def pop(self):
31 if self.is_empty():
32 raise StackUnderflow
33 return self._elems.pop()
34
35 #链表实现栈
36 class LStack(object):
37 def __init__(self):
38 self._top = None
39
40 def is_empty(self):
41 return self._top is None
42
43 def top(self):
44 if self.is_empty():
45 raise StackUnderflow("in LStack.top()")
46 return self._top.elem
47
48 def push(self, elem):
49 self._top = Node(elem, self._top)
50
51 def pop(self):
52 if self.is_empty():
53 raise StackUnderflow("in LStack.pop()")
54 result = self._top.elem
55 self._top = self._top.next
56 return result
57
58
59
60 if __name__=="__main__":
61 st1 = SStack()
62 st1.push(3)
63 st1.push(5)
64 while not st1.is_empty():
65 print(st1.pop())
66
67 print("============")
68 st2 = LStack()
69 st2.push(3)
70 st2.push(5)
71 while not st2.is_empty():
72 print(st2.pop())