#队列 #队列是一种先入先出（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<tail: #队尾后移 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())