棧是一種只能在同一端進行插入/刪除操作的線性表。表中允許進行插入/刪除操作的一端稱為棧頂。棧頂的當前位置是動態的，可以用一個稱為棧頂指針的位置指示器來指示。表的另一端稱為棧底。當棧中沒有元素時稱為空棧。棧的插入操作通常稱為進棧或入棧，棧的刪除操作通常稱為出棧或退棧。
棧的一大特點是 LIFO，即 Last In First Out。
抽象數據類型棧的定義如下：
數據對象： D = { a i ∣ 0 ≤ i ≤ n − 1 , n ≥ 0 } 數據關系： R = { r } r = { < a i , a i + 1 > ∣ a i , a i + 1 ∈ D , i = 0 , ⋯ , n − 2 } 基本運算： empty() ： 判 斷 棧 是 否 為 空 push(e) ： 將 e 壓 入 棧 中 pop() ： 取 出 棧 頂 元 素 gettop() ： 返 回 棧 頂 元 素 \begin{aligned} &\text{數據對象：} D=\{a_i|0\leq i\leq n-1,n\geq0\} \\ &\text{數據關系：} \\ &\quad R = \{r\} \\ &\quad r=\{<a_i,a_{i+1}>|a_i,a_{i+1}\in D,i=0,\cdots, n-2\} \\ &\text{基本運算：} \\ &\quad \text{empty()}：判斷棧是否為空 \\ &\quad \text{push(e)}：將 e 壓入棧中 \\ &\quad \text{pop()}：取出棧頂元素 \\ &\quad \text{gettop()}：返回棧頂元素 \\ \end{aligned} 數據對象：D={ ai∣0≤i≤n−1,n≥0}數據關系：R={ r}r={ <ai,ai+1>∣ai,ai+1∈D,i=0,⋯,n−2}基本運算：empty()：判斷棧是否為空push(e)：將e壓入棧中pop()：取出棧頂元素gettop()：返回棧頂元素
由於棧中元素的邏輯關系與線性表的相同，因此可以借鑒線性表的兩種存儲結構來存儲棧。
采用順序存儲結構來存儲時，用列表 data 來存放棧中的元素，稱為順序棧。由於Python列表提供了一端動態擴展的功能，為此將 data[0] 作為棧底，將 data[-1] 作為棧頂，其中 len(data) 代表棧中的元素個數。
接下來我們直接完整地實現順序棧的基本功能：
class SqStack:
def __init__(self):
self.data = []
def empty(self):
return len(self.data) == 0
def push(self, e):
self.data.append(e)
def pop(self):
assert not self.empty()
return self.data.pop()
def gettop(self):
assert not self.empty()
return self.data[-1]
從以上可以看出，棧的各種基本運算的時間復雜度均為 O ( 1 ) \mathcal{O}(1) O(1)。
假設用戶輸入的表達式中含有圓括號、方括號和花括號，並且只含這些括號。設計一個算法來判斷該表達式中的括號是否配對。
我們可以利用順序棧來解決這個問題：
def is_match(string):
stack = SqStack()
for e in string:
if e == '(' or e == '[' or e == '{':
stack.push(e)
else:
if e == ')':
if stack.empty() or stack.gettop() != '(':
return False
stack.pop()
if e == ']':
if stack.empty() or stack.gettop() != '[':
return False
stack.pop()
if e == '}':
if stack.empty() or stack.gettop() != '{':
return False
stack.pop()
return stack.empty()
string_1 = '([)]'
string_2 = '([])'
print(is_match(string_1))
# False
print(is_match(string_2))
# True
設計一個最小棧。即在原有棧結構的基礎上，添加一個 getmin() 方法，用於在 O ( 1 ) \mathcal{O}(1) O(1) 的時間內返回棧中的最小元素。
我們可以在原來的基礎上添加一個 mindata 列表，其中 data 列表表示主棧，mindata 列表表示輔助棧，用來存放當前最小元素（注：mindata 中可能有多個元素）。
class SqStack:
def __init__(self):
self.data = []
self.__mindata = []
""" min 棧的基本運算 """
def __minempty(self):
return len(self.__mindata) == 0
def __minpush(self, e):
self.__mindata.append(e)
def __minpop(self):
assert not self.__minempty()
return self.__mindata.pop()
def __mingettop(self):
assert not self.__minempty()
return self.__mindata[-1]
""" 主棧的基本運算 """
def empty(self):
return len(self.data) == 0
def push(self, e):
if self.empty() or e <= self.getmin():
self.__mindata.append(e)
self.data.append(e)
def pop(self):
assert not self.empty()
x = self.data.pop()
if x == self.__mingettop():
self.__minpop()
return x
def gettop(self):
assert not self.empty()
return self.data[-1]
def getmin(self):
assert not self.empty()
return self.__mindata[-1]
采用鏈式存儲結構的棧稱為鏈棧，這裡采用單鏈表來實現。
鏈棧的優點是不需要考慮棧滿溢出的情況。
如圖所示，首結點是棧頂結點，尾結點是棧底結點。該鏈棧的四要素如下：
head.next == None；鏈棧中的每個結點類型與普通單鏈表的一樣：
class LinkNode:
def __init__(self, data=None, next=None):
self.data = data
self.next = next
鏈棧類的設計如下：
class LinkStack:
def __init__(self):
self.head = LinkNode()
self.head.next = None
接下來我們在鏈棧中實現棧的基本運算：
class LinkStack:
def __init__(self):
self.head = LinkNode()
self.head.next = None
def empty(self):
return self.head.next == None
def push(self, e):
s = LinkNode(e)
s.next = self.head.next
self.head.next = s
def pop(self):
assert not self.empty()
p = self.head.next
self.head.next = p.next
return p.data
def gettop(self):
assert not self.empty()
return self.head.next.data
同一入棧序列可產生不同的出棧序列。例如，設入棧序列為 ( 1 , 2 , 3 , 4 , 5 ) (1,2,3,4,5) (1,2,3,4,5)，我們可以先讓 1 , 2 , 3 1,2,3 1,2,3 入棧、出棧，再讓 4 , 5 4,5 4,5 入棧、出棧，這樣得到的出棧序列是 ( 3 , 2 , 1 , 5 , 4 ) (3,2,1,5,4) (3,2,1,5,4)。我們還可以先讓 1 , 2 1,2 1,2 入棧、出棧，再讓 3 , 4 , 5 3,4,5 3,4,5 入棧、出棧，這樣得到的出棧序列是 ( 2 , 1 , 5 , 4 , 3 ) (2,1,5,4,3) (2,1,5,4,3)。
給定入棧序列 a，設計一個算法來判斷 b 是否是 a 的合法出棧序列（其中 a 和 b 均為 1 ∼ n 1\sim n 1∼n 的一個排列）。
我們只需模擬過程即可：
def is_valid(a, b):
stack = SqStack()
j = 0
for i in range(len(a)):
stack.push(a[i])
while not stack.empty() and stack.gettop() == b[j]:
stack.pop()
j += 1
return stack.empty()
print(is_valid([1, 2, 3, 4], [1, 3, 2, 4]))
# True
print(is_valid([1, 2, 3, 4], [4, 3, 1, 2]))
# False
本題非常簡單，無需過多解釋。
不過需要注意的是，為了簡單起見，我們直接用列表來模擬棧，不再單獨寫一個類了。
class Solution:
def simplifyPath(self, path: str) -> str:
stack = list()
for s in path.split('/'):
if s:
if s != '.' and s != '..':
stack.append(s)
if s == '..' and stack:
stack.pop()
return '/' + '/'.join(stack)
class Solution(object):
def asteroidCollision(self, asteroids):
stack = list()
for new in asteroids:
while stack and new < 0 < stack[-1]:
if stack[-1] < -new:
stack.pop()
continue
elif stack[-1] == -new:
stack.pop()
break
else:
stack.append(new)
return stack
具體思路是，首先找到中間結點，然後將鏈表的前半部分和後半部分切斷，再反轉後半部分的鏈表，最後合並兩個鏈表。
class Solution:
def reorderList(self, head: ListNode) -> None:
if not head:
return
mid = self.middleNode(head)
l1 = head
l2 = mid.next
mid.next = None
l2 = self.reverseList(l2)
self.mergeList(l1, l2)
def middleNode(self, head: ListNode) -> ListNode:
slow = fast = head
while fast.next and fast.next.next:
slow = slow.next
fast = fast.next.next
return slow
def reverseList(self, head: ListNode) -> ListNode:
prev = None
curr = head
while curr:
nextTemp = curr.next
curr.next = prev
prev = curr
curr = nextTemp
return prev
def mergeList(self, l1: ListNode, l2: ListNode):
while l1 and l2:
l1_tmp = l1.next
l2_tmp = l2.next
l1.next = l2
l1 = l1_tmp
l2.next = l1
l2 = l2_tmp
