栈:后进先出(LIFO)表。
特点:只允许在顶部进行存取操作的顺序表。
基本操作:
应用场景:
栈的链表实现:
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