资源简介

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

展开更多......

收起↑