如何在Python中反转任意队列的内容？
我对Python还比较陌生，想知道怎么反转一个队列。如果我理解得没错，队列就是一种数据结构，可以用任何语言来实现，比如在Python中用列表来表示。
所以如果题目要求反转一个栈或队列，但这两者都可以用列表来表示，那是不是就等于说要反转列表里的内容呢？我查了一下这个话题，发现通过使用类和方法，可以实现入队、出队和判断是否为空等操作。
class Queue:
def __init__(self):
self.items = []
def isEmpty(self):
return self.items == []
def enqueue(self, item):
self.items.insert(0,item)
def dequeue(self):
return self.items.pop()
那么如果我被要求反转一个队列的内容，这是不是意味着我只能通过上面提到的方法来反转列表里的内容？（也就是只能从列表的前面移除项目，然后再把项目添加到列表的后面）
3 个回答
0
使用另一个队列的简单方法
queue = [] # queue
queue.append(1) # adding items
queue.append(2)
queue.append(3)
print(queue) #original queue
queue_2 = []
for i in range(0,len(queue)):
queue_2.append(queue.pop())
print(queue_2) # reversed queue
- 用一个空的 Python 列表创建一个队列。
- 把项目添加到这个列表里。
- 再创建一个空的队列。
4. 使用一个 for 循环，把第一个队列里的值取出来，放到第二个队列里。
5. 完成了！！！
3
不需要栈！
注意，你需要能够找到队列的长度。我们可以用一个辅助队列来实现，通过弹出元素并计数，然后再把这些元素放回去。
注意，你可以通过反复进行
pop-push操作来轻松旋转队列。注意，你可以像这样交换索引
m和n：Have [ 1 2 3 ... m-1 m m+1 ... n-1 n n+1 ... x ] Want [ 1 2 3 ... m-1 n m+1 ... n-1 m n+1 ... x ] Rotate to n [ n+1 ... x 1 2 3 ... m-1 m m+1 ... n-1 n ] Pop into temporary storage [ n+1 ... x 1 2 3 ... m-1 m m+1 ... n-1 ] t = n Rotate to m [ m+1 ... n-1 n+1 ... x 1 2 3 ... m-1 m ] t = n Push from temporary storage [ n m+1 ... n-1 n+1 ... x 1 2 3 ... m-1 m ] Pop into temporary storage [ n m+1 ... n-1 n+1 ... x 1 2 3 ... m-1 ] t = m Rotate to n-1 [ n+1 ... x 1 2 3 ... m-1 n m+1 ... n-1 ] t = m Push from temporary storage [ n+1 ... x 1 2 3 ... m-1 n m+1 ... n-1 m ] Rotate to x [ 1 2 3 ... m-1 n m+1 ... n-1 m n+1 ... x ]这样我们就可以在
O(len(queue))的时间内交换位置m和n。不断交换第
n个和第len(queue)-n个元素，直到n ≥ len(queue)-n。
所以这里是：
class Queue:
def __init__(self):
self.items = []
def isEmpty(self):
return self.items == []
def enqueue(self, item):
self.items.insert(0,item)
def dequeue(self):
return self.items.pop()
# For visualisation
def __repr__(self):
return repr(self.items)
找长度的程序：
def queue_length(queue):
length = 0
auxillary = Queue()
while not queue.isEmpty():
length += 1
auxillary.enqueue(queue.dequeue())
while not auxillary.isEmpty():
queue.enqueue(auxillary.dequeue())
return length
旋转的程序：
def rotate(queue, n):
for _ in range(n):
queue.enqueue(queue.dequeue())
交换的程序：
def swap(queue, m, n):
length = queue_length(queue)
# Make sure m ≤ n
if m > n:
m, n = n, m
# Rotate to n
rotate(queue, length-n-1)
# Pop into temporary storage
temp = queue.dequeue()
# Rotate to m
rotate(queue, n-m-1)
# Swap
queue.enqueue(temp)
temp = queue.dequeue()
# Rotate to where n was
rotate(queue, m-n-1+length)
# Push back
queue.enqueue(temp)
# Rotate to start
rotate(queue, n)
反转的程序：
def reverse(queue):
left = 0
right = queue_length(queue)-1
while left < right:
swap(queue, left, right)
left += 1
right -= 1
测试用：
queue = Queue()
for i in reversed(range(20)):
queue.enqueue(i)
queue
#>>> [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19]
reverse(queue)
queue
#>>> [19, 18, 17, 16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0]
注意，这可以通过找到更简单的交换方式来加快速度；
[ a b c d e f g ]
→ [ b c d e f g a ]
→ [ c d e f g b a ]
→ [ d e f g c b a ]
→ [ e f g d c b a ]
→ [ f g e d c b a ]
→ [ g f e d c b a ]
所以我们有了“把索引 0 推到索引 n”的程序。
这只是
def shift_head(queue, n):
length = queue_length(queue)
# Rotate head to end and pop
rotate(queue, length-1)
temp = queue.dequeue()
# Insert in position n
rotate(queue, length-n-1)
queue.enqueue(temp)
# Rotate back
rotate(queue, n)
给出
def quickreverse(queue):
push_to = queue_length(queue)
while push_to:
shift_head(queue, push_to)
push_to -= 1
这个有效：
queue
#>>> [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19]
quickreverse(queue)
queue
#>>> [19, 18, 17, 16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0]
7
你可以使用一个辅助栈来反转你的队列中的元素。
简单来说，你会把队列里的每个元素一个个放到栈里，直到队列变空。然后，你再一个个从栈里取出元素，并把它们放回队列，直到栈也变空。
# suppose your have a Queue my_queue
aux_stack = Stack()
while not my_queue.isEmpty():
aux_stack.push(my_queue.dequeue())
while not aux_stack.isEmpty():
my_queue.enqueue(aux_stack.pop())