"""
给定正整数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 = 0
def empty(self):
'''
:Desc
判队空
:return:
如果队为空，返回True
如果队不为空，返回False
'''
return self.front == self.rear
def push(self,val):
'''
:Desc
入队
:param
val:待入队关键字
'''
# 如果队列满了，抛出异常
if (self.rear + 1) % self.max == self.front:
raise IndexError("队列为满")
# 在队尾插入新的关键字
self.data[self.rear] = val
# 修改队尾指针
self.rear = (self.rear + 1) % self.max
def pop(self):
'''
:Desc
将队首元素出队
'''
# 如果队列为空，抛出异常
if self.empty():
raise IndexError("队列为空")
# 队列不为空，获取队首元素
cur = self.data[self.front]
# 修改队首指针，指向下一个位置
self.front = (self.front + 1) % self.max
# 返回原队首元素
return cur
def 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.front
def traversal(self):
"""
:Desc
遍历
"""
if self.empty():
raise IndexError("队列为空")
if self.front < self.rear:
curindex = self.front
while curindex < self.rear:
print(self.data[curindex],end=" ")
curindex += 1
else:
curindex = self.front
while curindex < self.max:
print(self.data[curindex],end=" ")
curindex += 1
curindex =0
while curindex < self.rear:
print(self.data[curindex],end=" ")
curindex += 1
print()
def traversal2(self):
"""
:Desc
遍历
"""
if self.empty():
raise IndexError("队列为空")
if self.front < self.rear:
curindex = self.front
while curindex < self.rear:
if self.data[curindex] != 0:
print(self.data[curindex],end=" ")
curindex += 1
else:
curindex = self.front
while curindex < self.max:
if self.data[curindex] != 0:
print(self.data[curindex],end=" ")
curindex += 1
curindex =0
while curindex < self.rear:
if self.data[curindex] != 0:
print(self.data[curindex],end=" ")
curindex += 1
print()
def top(self):
"""
:Desc
返回队首元素
"""
if not self.empty():
return self.data[self.front]
return
def length(self):
"""
:Desc
获取队列长度
"""
size = 0
for i in range(self.front,self.rear):
size += 1
return size
if __name__ == '__main__':
n = 5
qu = CircleQueue()
length = None
for 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)
