# deque双边队列，被设计成可以在两端进行插入和读取的特殊list
# 其在list的基础上增加了移动、旋转、增删等操作
from collections import deque
d = deque([0])
# extend() 方法在原有list上逐个扩展增加新元素，不会生成新的list,因而不能用于链式表达式
d.extend(["hello", 1,2,3,4,5])
print(d)
deque([0, 'hello', 1, 2, 3, 4, 5])
# append()方法将新增的元素当作一个整体添加到原有list上
d.append([6,7])
print(d)
deque([0, 'hello', 1, 2, 3, 4, 5, [6, 7]])
# 在左边插入
d. appendleft(-1)
print(d)
deque([-1, 0, 'hello', 1, 2, 3, 4, 5, [6, 7]])
d.pop() # 从右边删除一个元素
print(d)
deque([-1, 0, 'hello', 1, 2, 3, 4, 5])
d.popleft() #从左边删除一个元素
print(d)
deque([0, 'hello', 1, 2, 3, 4, 5])
d.extendleft([6])
print(d)
deque([6, 0, 'hello', 1, 2, 3, 4, 5])
d.popleft()
print(d)
deque([0, 'hello', 1, 2, 3, 4, 5])
d.remove('hello')
print(d)
deque([0, 1, 2, 3, 4, 5])
# 支持in操作
print(5 in d)
print(6 in d)
True
False
#可以直接使用range()初始化列表
dd = deque(range(1, 11))
print(dd)
deque([1, 2, 3, 4, 5, 6, 7, 8, 9, 10])
#逆时针旋转
dd.rotate(-3)
print(dd)
deque([4, 5, 6, 7, 8, 9, 10, 1, 2, 3])
#顺时针旋转
dd.rotate(3)
print(dd)
deque([1, 2, 3, 4, 5, 6, 7, 8, 9, 10])
# 整个队列旋转
dd.reverse()
print(dd)
deque([10, 9, 8, 7, 6, 5, 4, 3, 2, 1])
约瑟夫算法
据说著名犹太历史学家 Josephus有过以下的故事：在罗马人占领乔塔帕特后，39 个犹太人与Josephus及他的朋友躲到一个洞中，39个犹太人决定宁愿死也不要被敌人抓到，于是决定了一个自杀方式：41个人排成一个圆圈，由第1个人开始报数，每报数到第3人该人就必须自杀，然后再由下一个重新报数，直到所有人都自杀身亡为止。然而Josephus 和他的朋友并不想遵从。首先从一个人开始，越过k-2个人（因为第一个人已经被越过），并杀掉第k个人。接着，再越过k-1个人，并杀掉第k个人。这个过程沿着圆圈一直进行，直到最终只剩下一个人留下，这个人就可以继续活着。问题是一开始要站在什么地方才能避免自杀？Josephus要他的朋友先假装遵从，他将朋友与自己安排在第16个与第31个位置，于是逃过了这场死亡游戏。
# 使用deque()解决约瑟夫问题
from collections import deque
def ysf(n,k):
dq = deque(range(1,n+1))
while dq:
dq.rotate(-k)
print(dq.pop(), end=" ")
ysf(9,2)
2 4 6 8 1 5 9 7 3
ysf(41,3)
3 6 9 12 15 18 21 24 27 30 33 36 39 1 5 10 14 19 23 28 32 37 41 7 13 20 26 34 40 8 17 29 38 11 25 2 22 4 35 16 31
