文章目錄

• 棧（Stack）
• 棧的實現
• 棧的應用
• • LeetCode 20th（有效的括號）
  • LeetCode 405. 數字轉換為十六進制數

---

棧（Stack）

棧是一個有次序的數據集，每個數據項僅從”棧頂“一端加入到數據集中、從數據集中移除，棧具有后進先出（LIFO）特性。

• 在棧中，數據項的加入和移除都僅發生在同一端；這一端叫做棧頂top，另一端叫棧底base；
• 距離棧底越近的數據，留在棧中的時間越長；
• 后進先出LIFO特性；
• 翻轉次序，進棧和出棧的次序正好相反。

ls = [1,2,3,'dog',5,6,7,8] s = Stack() for i in ls:s.push(i) while not s.isEmpty():print(s.pop())

棧的實現

數組（列表實現）棧。

# 創建一個空棧，不包含任何數據 class Stack(object):def __init__(self):self.items = []# 返回棧是否為空def isEmpty(self):return self.items == []# 將數據添加到棧頂def push(self, item):self.items.append(item)#將棧頂數據移除def pop(self):return self.items.pop()# 返回棧頂數據，不修改棧def peek(self):return self.items[len(self.items)-1]# 返回棧中數據長度def size(self):return len(self.items) from ADT_CLASS import Stacks = Stack() print(s.isEmpty()) s.push(1) s.push('cat') print(s.peek()) s.push(3) print(s.size()) s.push(4) print(s.pop()) print(s.pop()) print(s.size()) 輸出： True cat 3 4 3 2

棧的應用

LeetCode 20th（有效的括號）

給定一個只包括 ‘(’，’)’，’{’，’}’，’[’，’]’ 的字符串 s ，判斷字符串是否有效。

有效字符串需滿足：

• 左括號必須用相同類型的右括號閉合。
• 左括號必須以正確的順序閉合。

from ADT_CLASS import Stackdef isValid(s):stack = Stack()com = Trueindex = 0while index < len(s) and com:if s[index] in '([{':stack.push(s[index])else:if stack.isEmpty():com = Falseelse:l = stack.pop()if not matches(l, s[index]):com = Falseindex += 1if com and stack.isEmpty():return Trueelse:return False def matches(l,r):opens = '([{'closers = ")]}"return opens.index(l) == closers.index(r)

LeetCode 405. 數字轉換為十六進制數

進制轉換：
二進制有兩個不同數字：0,1
八進制有八個不同數字：0,1,2,3,4,5,6,7
十六進制有十六個不同數字：0,1,2,3,4,5,6,7,8,9,A,B,C,D,E,F

在代碼中我們可以通過調參base實現不同進制轉換。

from ADT_CLASS import Stack def toConverter(num, base):digits = '0123456789ABCDEF's = Stack()while num > 0:cur = num % bases.push(cur)num = num // baseans = ''while not s.isEmpty():ans += digits[s.pop()]return ans

注意：這里我們只處理了num>0的轉換情況，如果是小于等于0的數需要另外討論。
ADT_CLASS為我寫的類文件，這樣在使用的時候導入就可以了，比較方便。

總結

以上是生活随笔為你收集整理的栈及其python实现的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。