（一）堆疊
1、堆疊是一種后進先出，先進后出的資料結構，
2、堆疊是一種操作受限的線性表，只允許在一端插入和洗掉資料，
3、堆疊主要包含2個操作，入堆疊和出堆疊
4、堆疊可以用陣列實作，也可以用鏈表實作，用陣列實作的堆疊叫做順序堆疊，用鏈表實作的堆疊叫做鏈式堆疊，
例如：
現在有一個空瓶子，
1、我們依次放入多個蘋果
2、從瓶子中取蘋果的時候，最后放進去的蘋果會最先取出來，最先放進去的蘋果最后取出來，
3、只能從瓶口放入或取出蘋果，（只允許在一端插入和洗掉資料）
用陣列實作一個堆疊：（這里用串列代替了）
1 class ArrayStack(): 2 3 ITEMS = [] # 這里用串列代替了 4 COUNT = 0 # 堆疊中的元素個數 5 N = 10 # 堆疊的大小 6 7 def push(self ,item): 8 """ 9 入堆疊 10 :param item: 11 :return: 12 """ 13 if len(self.ITEMS) >= self.N: return False # 堆疊已經滿了 14 self.ITEMS.append(item) 15 self.COUNT += 1 16 return True 17 18 def pop(self): 19 """ 20 出堆疊 21 :return: 22 """ 23 if len(self.ITEMS) == 0: return False # 堆疊為空 24 item = self.ITEMS.pop() 25 self.COUNT -= 1 26 return item
（二）佇列
1、佇列是一種先進先出的資料結構，例如：超市排隊付款，排在前面的先付完款，然后先出去，后來的只能排隊，不允許插隊，
2、堆疊只支持2個基本操作入堆疊（push）和出堆疊（pop），佇列也只支持2個基本操作，入隊 enqueue()，放一個資料到佇列尾部；出隊 dequeue()，從佇列頭部取一個元素，
3、佇列和堆疊一樣，也是一種操作受限的線性表結構，
4、跟堆疊一樣，也可以用陣列或鏈表實作，用陣列實作的佇列叫順序佇列，用鏈表實作的佇列叫鏈式佇列，
用陣列實作一個佇列（這里用串列代替了）：
1 class ArrayQueue(): 2 3 ITEMS = [] # 陣列 4 HEAD = 0 # 隊頭索引 5 TAIL = 0 # 隊尾索引 6 7 def __init__(self,n): 8 self.n = n # 陣列大小 9 10 def enqueue(self,item): 11 """ 12 入隊 13 :param item: 14 :return: 15 """ 16 if self.TAIL == self.n: return False # 隊尾索引等于陣列大小，表示佇列滿了 17 self.ITEMS.append(item) 18 self.TAIL += 1 19 return True 20 21 def dequeue(self): 22 """ 23 出隊 24 :return: 25 """ 26 if self.HEAD == self.TAIL: return False # 隊頭索引==隊尾索引，表示佇列為空 27 item = self.ITEMS[self.HEAD] 28 self.ITEMS[self.HEAD] = "X" # 標識已經洗掉 29 self.HEAD += 1 30 return item
（三）練習題
1、leetcode 20
1 class Solution: 2 def isValid(self, s: str) -> bool: 3 the_dict = {"(":")","{":"}","[":"]","k":"k"} 4 stack = ["k"] 5 for i in s: 6 if i in the_dict: stack.append(i) # 將左括號壓入堆疊 7 elif the_dict[stack.pop()] != i: return False # 如果字串中的右括號不等于預期的右括號，回傳false 8 return len(stack) == 1
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/145716.html
標籤：Python
上一篇：使用xadmin搜索search_fields報錯:Related Field got invalid lookup: icontains