数据结构Python用队列实现杨辉三角形

简介

队列是一种特殊的线性表，特殊之处在于它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作，和栈一样，队列是一种操作受限制的线性表。进行插入操作的端称为队尾，进行删除操作的端称为队头。队列中没有元素时，称为空队列。

队列的数据元素又称为队列元素。在队列中插入一个队列元素称为入队，从队列中删除一个队列元素称为出队。因为队列只允许在一端插入，在另一端删除，所以只有最早进入队列的元素才能最先从队列中删除，故队列又称为先进先出（FIFO—first in first out）线性表。杨辉三角形

python代码实现

"""给定正整数n，利用一个队列输出n阶杨辉三角形。"""class CircleQueue(object):def __init__(self,max=50):# 队列最大容量self.max = max# 存储队列元素的数组self.data = [None for i in range(self.max)]# 队首指针self.front = 0# 队尾指针self.rear = 0def empty(self):''':Desc判队空:return:如果队为空，返回True如果队不为空，返回False'''return self.front == self.reardef push(self,val):''':Desc入队:paramval:待入队关键字'''# 如果队列满了，抛出异常if (self.rear + 1) % self.max == self.front:raise IndexError("队列为满")# 在队尾插入新的关键字self.data[self.rear] = val# 修改队尾指针self.rear = (self.rear + 1) % self.maxdef pop(self):''':Desc将队首元素出队'''# 如果队列为空，抛出异常if self.empty():raise IndexError("队列为空")# 队列不为空，获取队首元素cur = self.data[self.front]# 修改队首指针，指向下一个位置self.front = (self.front + 1) % self.max# 返回原队首元素return curdef peek(self):''':Desc获取队首元素:return:返回队首元素'''# 如果队列为空，抛出异常if self.empty():raise IndexError("队列为空")# 返回队首元素return self.data[self.front]def notEmpty(self):""":Desc判断队列是否已满"""return (self.rear + 1) % self.max == self.frontdef traversal(self):""":Desc遍历"""if self.empty():raise IndexError("队列为空")if self.front < self.rear:curindex = self.frontwhile curindex < self.rear:print(self.data[curindex],end=" ")curindex += 1else:curindex = self.frontwhile curindex < self.max:print(self.data[curindex],end=" ")curindex += 1curindex =0while curindex < self.rear:print(self.data[curindex],end=" ")curindex += 1print()def traversal2(self):""":Desc遍历"""if self.empty():raise IndexError("队列为空")if self.front < self.rear:curindex = self.frontwhile curindex < self.rear:if self.data[curindex] != 0:print(self.data[curindex],end=" ")curindex += 1else:curindex = self.frontwhile curindex < self.max:if self.data[curindex] != 0:print(self.data[curindex],end=" ")curindex += 1curindex =0while curindex < self.rear:if self.data[curindex] != 0:print(self.data[curindex],end=" ")curindex += 1print()def top(self):""":Desc返回队首元素"""if not self.empty():return self.data[self.front]returndef length(self):""":Desc获取队列长度"""size = 0for i in range(self.front,self.rear):size += 1return sizeif __name__ == '__main__':n = 5qu = CircleQueue()length = Nonefor i in range(1,n+1):if i == 1:qu.push(0)qu.push(i)qu.push(0)qu.traversal2()tmp = []while not qu.empty():val = qu.pop()tmp.append(val)tmp.append(0)tmp = [tmp[i] + tmp[i - 1] for i in range(len(tmp))]for v in tmp:qu.push(v)