數據結構（二）：棧

棧：後進先出（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