标签 栈 下的文章 - 叁零零肆零肆

队列和栈 1.队列的特性1)队列是一种先入先出（FIFO）的线性表。2)队列有两个指针，允许插入的一端为队尾tail，允许删除的一段为队首head。由于无法中间插入和删除，故其操作是受限的。3)队列只规定了插入和删除的方式，但并未规定其存储结构，所以队列既可以用数组实现，又可以用链表实现。2.创建队列head = 0 #队首指针 tail = 0 #队尾指针 que = ['']*4 #存储空间（数组方式）3.入队que[tail] = 'a' #从队尾入队 tail += 1 #队尾后移 que[tail] = 'b' tail += 1 que[tail] = 'c' tail += 1 que[tail] = 'd' tail += 1 4.出队if head<tail: print(que[head]) #输出队首内容，出队 head += 1 #队首后移 #操作发现此时tail=4已经无法在插入数据，但实际上que[0]数据已出队，存储空间可用，这种情况称为假溢出。对于存储空间有限的情况，可用循环队列增加存储空间的利用率。5.循环队列入队if tail-head<4: que[tail%4] = 'e' #通过取模运算实现存储空间复用 tail += 1 #队尾的数值继续累加 else: print("存储空间已满，等待出队中") #注意：此时tail的值已经超出索引范围，但只要保证头尾之前的存储空间不超过数组范围，就可以用取模的方式实现空间复用而不会覆盖未出队的数据。6.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,否则返回False7.拓展：队列的类实现方式#节点类 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"->" #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())8.栈的特性1)栈是一种先入后出（FILO）的线性表。2)栈只有一个指针top，指向栈顶，插入和删除都在栈顶完成。同样也由于无法中间插入和删除，故其操作是受限的。3)栈只规定了插入和删除的方式，但并未规定其存储结构，所以栈也可用数组或链表实现。9.创建栈top = -1 #栈顶 st = ['']*4 #栈空间10.入栈top += 1 st[top] = 'a' top += 1 st[top] = 'b' top += 1 st[top] = 'c' top += 1 st[top] = 'd'11.出栈if top>-1: print(st[top]) top -= 112.python列表操作函数实现拟栈操作stacklist = [] #空列表 stacklist.append("A") #追加，入栈 stacklist.pop() #删除最后一个，出栈13.补充案例：逆波兰式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))14.拓展：栈的类实现方式#节点类 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"->" #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())15.广度优先搜索和深度优先搜索（省编作业本P31）1)广度优先算法(输出站点顺序)maxn = 8 #总站点数量 a = [[0,1,0,1,0,0,0,0], [0,0,1,0,0,0,0,0], [0,0,0,0,0,1,0,0], [0,0,0,0,1,0,1,0], [0,0,1,0,0,1,0,0], [0,0,0,0,0,0,0,1], [0,0,0,0,0,0,0,1], [0,0,0,0,0,0,0,0]] #站点之间的连接关系(连通矩阵) q = [0]*200; head = tail = 0 #队列初始化 f = [False]*maxn #用于站点查重 start = 0 q[tail]=[start,-1];tail+=1 #起始站点入队 f[start] = True #去重 layer_q = tail end = 7 ans = 0; flag = False #记录转车次数,达到标志记为False while head<tail and flag==False: c = q[head][0] #当前站点出队 head += 1 # f[c] = False #清空经过标记 if layer_q == head-1: ans += 1 layer_q = tail #更新位置 for j in range(maxn): if j!=end and a[c][j]==1 and f[j]==False: # j站点不是终点，但和C站点连通，并且未经过 q[tail]=[j,head-1]; tail+=1 #入队 f[j] = True #标记 if j==end and a[c][j]==1: q[tail]=[j,head-1]; tail+=1 #入队 flag = True break p = tail-1; s = '' while p != -1: s += str(q[p][0])+"<-" #由于在节点增加了指针域，所以可以顺序输出结果 p = q[p][1] print("换乘顺序:"+s+"共换乘:"+str(ans)+"次") 2)深度优先算法(求全部可行路径)maxn = 8 #总站点数量 a = [[0,1,0,1,0,0,0,0], [0,0,1,0,0,0,0,0], [0,0,0,0,0,1,0,0], [0,0,0,0,1,0,1,0], [0,0,1,0,0,1,0,0], [0,0,0,0,0,0,0,1], [0,0,0,0,0,0,0,1], [0,0,0,0,0,0,0,0]] #站点之间的连接关系 start = 0 #起始站点 end = 7 #结束站点 s = [] #存放中间经过的站点 min_ = 100 #存放最小值 s.append(0) #始发站入栈 def find(start): global end,s,min_ for i in range(maxn): if a[start][i] == 1: s.append(i) if i == end: print(s) #输出换乘顺序 if len(s)<min_: min_ = len(s) else: find(i) s.pop() find(start) print(min_-2) #输出最少换乘次数，总站点数减去起点和终点