一、实验目的
1．掌握用Python定义队列的顺序存储结构和链式存储结构，以便在实际背景下灵活运用；
2．掌握队列的特点，即先进先出的原则；
3．掌握队列的基本操作实现方法。
二、实验环境
1．Windows操作系统的计算机
2．Python3.7环境平台和PyCharm编辑器
三、实验说明
1．实现队列的顺序存储结构和链式存储结构的基本操作。
2．注意队满、队空条件及入队、出队时的指针的改变。
3．实验中如无特别说明，均要求使用脚本（.py）方式编写代码。
4．自主编写程序，必要时参考相关资料。
5．实验学时：2学时
四、实验内容和步骤
1．实验内容
（1） 基础实验题
设计整数循环队列和整数链队的基本运算程序，并用相关数据进行测试。
参考框架：
#整数循环队列
class CSqQueue: #循环队列类
def __init__(self): #构造方法
def empty(self): #判断队列是否为空
def push(self,e): #元素e进队
def pop(self): #出队元素
def gethead(self): #取队头元素
if __name__ == '__main__':
print()
print(" 创建空循环队列qu")
_
print(" qu：","空" if qu.empty() else "不空")
print(" 进队1-4")
_
_
_
_
print(" qu：","空" if qu.empty() else "不空")
print(" 出队顺序:",end=' ')
while not qu.empty():
_
print()
print(" qu：","空" if qu.empty() else "不空")
print()
#整数链队
class LinkNode: #链队结点类
def __init__(self,data=None): #构造方法
class LinkQueue: #链队类
def __init__(self): #构造方法
def empty(self): #判断队是否为空
def push(self,e): #元素e进队
def pop(self): #出队操作
def gethead(self): #取队顶元素操作
if __name__ == '__main__':
print()
print(" 创建空链队qu")
_
print(" qu：","空" if qu.empty() else "不空")
print(" 进队1-4")
_
_
_
_
print(" qu：","空" if qu.empty() else "不空")
print(" 出队顺序:",end=' ')
while not qu.empty():
_
print()
print(" qu：","空" if qu.empty() else "不空")
print()
（2） 应用实验题
分别采用循环队列和链队实现杨辉三角形的输出。杨辉三角形的特点是两个腰上的数字都为1，其他位置上的数字是其上一行中与之相邻（上部和左上部）的两个整数之和。例如，当n=5时，打印的杨辉三角形如下：
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
参考框架：
from CSqQueue import CSqQueue
from LinkQueue import LinkQueue
from LinkQueue import LinkQueue
def yang_hui_CQ(n): #采用循环队列
line = CSqQueue ()
line.push(1) # 第 1行的 1个数入队
for i in range(1, n+1): # 输出三角形的前 n 行
_
for j in range(1, i + 1): #对于i行j列的元素
……
line.push(1) # 上面的循环只生成了i+1行的前i个数，最后一个数1入队
print() # 换行
def yang_hui_LQ(n): #采用链队
line = LinkQueue()
line.push(1) # 第 1行的 1个数入队
for i in range(1, n+1): # 输出三角形的前 n 行
_
for j in range(1, i + 1): #对于i行j列的元素
……
line.push(1) # 上面的循环只生成了i+1行的前i个数，最后一个数1入队
print() # 换行
if __name__ == "__main__":
yang_hui_CQ(7)
print()
yang_hui_LQ(7)
2．实验步骤
（1）分析实验内容，写出程序大致框架或完整的程序代码。
（2）进入Python集成环境。
（3）编辑程序并进行保存。
（4）运行程序，若有错误，修改错误后再次运行，如此反复进行到不显示出错为止。
（5）检查程序输出结果。
五、实验代码与结果（程序运行代码及其结果）
1． （1）给出算法的基本设计思想。
（2）根据设计思想，采用Python语言描述算法，关键之处给出注释。
class CSqQueue: #循环队列类
def __init__(self, maxsize): #构造方法
self.maxsize = maxsize
self.queue = [None] * maxsize
self.head = 0
self.tail = 0
def empty(self): #判断队列是否为空
return self.head == self.tail
def push(self, e): #元素e进队
if (self.tail + 1) % self.maxsize == self.head:
print("Queue is full!")
return False
self.queue[self.tail] = e
self.tail = (self.tail + 1) % self.maxsize
return True
def pop(self): #出队元素
if self.empty():
print("Queue is empty!")
return None
e = self.queue[self.head]
self.head = (self.head + 1) % self.maxsize
return e
def gethead(self): #取队头元素
if self.empty():
print("队列为空")
return None
return self.queue[self.head]
if __name__ == '__main__':
qu = CSqQueue(5)
print("创建空循环队列qu")
print("qu：","空" if qu.empty() else "不空")
print("进队1-4")
qu.push(1)
qu.push(2)
qu.push(3)
qu.push(4)
print("qu：","空" if qu.empty() else "不空")
print("出队顺序:",end=' ')
while not qu.empty():
print(qu.pop(), end=" ")
print()
print("qu：","空" if qu.empty() else "不空")
class LinkNode: #链队结点类
def __init__(self, data=None): #构造方法
self.data = data
self.next = None
class LinkQueue: #链队类
def __init__(self): #构造方法
self.head = None
self.tail = None
def empty(self): #判断队是否为空
return self.head is None
def push(self, e): #元素e进队
node = LinkNode(e)
if self.tail is None:
self.head = self.tail = node
else:
self.tail.next = node
self.tail = node
def pop(self): #出队操作
if self.empty():
print("队列为空")
return None
e = self.head.data
self.head = self.head.next
if self.head is None:
self.tail = None
return e
def gethead(self): #取队顶元素操作
if self.empty():
print("Queue is empty!")
return None
return self.head.data
if __name__ == '__main__':
qu = LinkQueue()
print("创建空链队qu")
print("qu：","空" if qu.empty() else "不空")
print("进队1-4")
qu.push(1)
qu.push(2)
qu.push(3)
qu.push(4)
print("qu：","空" if qu.empty() else "不空")
print("出队顺序:",end=' ')
while not qu.empty():
print(qu.pop(), end=" ")
print()
print("qu：","空" if qu.empty() else "不空")
2． （1）给出算法的基本设计思想。
（2）根据设计思想，采用Python语言描述算法，关键之处给出注释。
from CSqQueue import CSqQueue
from LinkQueue import LinkQueue
def yang_hui_CQ(n):
"""采用循环队列实现杨辉三角形的输出"""
line = CSqQueue(20) # 创建一个长度为20的循环队列，可根据数据规模自行调整
line.push(1) # 第一行的1入队
for i in range(n):
for j in range(i): # 每行输出i个数
e1 = line.pop() # 出队上方元素
if j == 0: # 第一个元素不需要加法
e2 = 0
else:
e2 = line.gethead() # 获取左上方元素，不出队
e3 = e1 + e2 # 计算当前元素的值
print(e3, end=" ")
line.push(e3) # 当前元素入队
line.push(1) # 行末元素入队
print() # 换行输出
def yang_hui_LQ(n):
"""采用链队实现杨辉三角形的输出"""
line = LinkQueue() # 创建一个空链队
line.push(1) # 第一行的1入队
for i in range(n):
for j in range(i): # 每行输出i个数
e1 = line.pop() # 出队上方元素
if j == 0: # 第一个元素不需要加法
e2 = 0
else:
e2 = line.gethead() # 获取左上方元素，不出队
e3 = e1 + e2 # 计算当前元素的值
print(e3, end=" ")
line.push(e3) # 当前元素入队
line.push(1) # 行末元素入队
print() # 换行输出
if __name__ == "__main__":
print("循环队列杨辉三角：")
yang_hui_CQ(3)
print()
print("链队杨辉三角：")
yang_hui_LQ(3)