資源簡介

#隊列
#隊列是一種先入先出（FIFO）的線性表。
#隊列有兩個指針，允許插入的一端為隊尾tail，允許刪除的一段為隊首head。由于無法中間插入和刪除，故其操作是受限的。
#隊列只規定了插入和刪除的方式，但并未規定其存儲結構，所以隊列既可以用數組實現，又可以用鏈表實現。
#1.創建隊列
head = 0 #隊首指針
tail = 0 #隊尾指針
que = ['']*4 #存儲空間（數組方式）
#2.入隊
que[tail] = 'a' #從隊尾入隊
tail += 1 #隊尾后移
que[tail] = 'b' #從隊尾入隊
tail += 1 #隊尾后移
que[tail] = 'c' #從隊尾入隊
tail += 1 #隊尾后移
que[tail] = 'd' #從隊尾入隊
tail += 1 #隊尾后移
#3.出隊
if head print(que[head]) #輸出隊首內容，出隊
head += 1 #隊首后移
#4.循環隊列以及假溢出問題
#根據上面的操作，我們發現此時tail=4,已經無法在插入數據，但實際上que[0]的數據已經出隊，存儲空間可用，這種情況便稱之為“假溢出”。
#對于存儲空間有限的情況，可以使用循環隊列增加存儲空間的利用率。
#循環隊列入隊
if tail-head<4:
que[tail%4] = 'e' #通過取模運算實現存儲空間復用
tail += 1 #隊尾的數值繼續累加
else:
print("存儲空間已滿，等待出隊中")
#注意：此時tail的值已經超出索引范圍，但只要保證頭尾之前的存儲空間不超過數組范圍，就可以用取模的方式實現空間復用而不會覆蓋未出隊的數據。
#python自帶的隊列模塊
import queue
q = queue.Queue(10) #生成一個存儲空間為10的隊列q
q.put("A") #入隊
q.put("B") #入隊
print(q.qsize()) #輸出隊列中的元素的個數
print(q.get()) #隊首元素出隊，出隊的元素為'A'
print(q.qsize()) #輸出隊列中的元素的個數
print(q.empty()) #判斷隊列是否為空,空則返回True,否則返回False
print(q.full()) #判斷隊列是否為滿,滿則返回True,否則返回False
#（堆）棧是一種先入后出（FILO）的線性表
#（堆）棧有只有一個指針top，指向棧頂，插入和刪除都在棧頂完成。同樣也由于無法中間插入和刪除，故其也操作是受限的。
#（堆）棧也只規定了插入和刪除的方式，但并未規定其存儲結構，所以棧也可以用數組或鏈表實現。
#1.創建棧
top = -1 #棧頂
st = ['']*4 #棧空間
#2.入棧
top += 1
st[top] = 'a'
top += 1
st[top] = 'b'
top += 1
st[top] = 'c'
top += 1
st[top] = 'd'
#3.出棧
if top>-1:
print(st[top])
top -= 1
#補充案例：逆波蘭式
def compValues(postorde_exp):
operators = "+-*/"
st = []
exp_list = postorde_exp.split()
print(exp_list)
for x in exp_list:
if x not in operators:
st.append(x)
else:
b = st.pop()
a = st.pop()
c = eval(a + x + b) #注意轉換方式
st.append(str(c))
return st.pop()
exp = "5 2 13 + * 59 -"
print(compValues(exp))
#python列表操作函數實現擬棧操作
stacklist = [] #空列表
stacklist.append("A") #追加，入棧
stacklist.pop() #刪除最后一個，出棧
拓展1：隊列的類實現方式
#節點類
class Node_class: #定義單節點類
def __init__(self,data_,next_=None): #注意默認值的使用
self.data = data_
self.next = next_
#隊列類
class Queue_class: #定義隊列類
def __init__(self): #生成實例初始化設置
self.head = None #隊首
self.tail = None #隊尾
self.size = 0 #定義隊列大小屬性，在入隊和出隊時直接修改
def __str__(self): #類實例字符串格式輸出設置
s = ""
cur=self.head
while cur is not None:
s += f"{cur.data}->" #format方法變種,與等價"{}->".format(cur.data)
cur=cur.next
return s[:-2] #刪除多余的"->"
def put(self,data_):
if self.tail is None or self.head is None:
self.tail = Node_class(data_)
self.head = self.tail
else:
self.tail.next = Node_class(data_)
self.size += 1
def get(self):
try:
a = self.head.data
self.head = self.head.next
self.size -= 1
except:
a = "隊列為空"
return a

q = Queue_class()
q.put("a")
print(q)
print(q.size)
print(q.get())
拓展2：（堆）棧的類實現方式
#節點類
class Node_class: #定義單節點(雙向節點)類
def __init__(self,data_,prev_=None,next_=None): #注意默認值的使用
self.data = data_
self.prev = prev_
self.next = next_
#（堆）棧類
class Stack_class: #定義棧類
def __init__(self): #生成實例初始化設置
self.head = None
self.size = 0
def __str__(self): #類實例字符串格式輸出設置
s = ""
cur=self.head
while cur is not None:
s += f"{cur.data}->" #format方法變種,與等價"{}->".format(cur.data)
cur=cur.next
return s[:-2] #刪除多余的"->"
def put(self,data_):
if self.head is None:
self.head = Node_class(data_)
else:
self.head = Node_class(data_,self.head)
self.head.prev.next = self.head
self.size += 1
def get(self):
try:
a = self.head.data
self.head = self.head.prev
self.size -= 1
except:
a = "棧為空"
return a
q = Stack_class()
q.put("a")
print(q)
print(q.size)
print(q.get())

展開更多......

收起↑