0
  • 接受用户的项目并创建一个队列，直到用户输入 -1
  • 打印队列
  • 反转给定的队列
  • 打印修改后的队列

例如输入可能是

  • 1
  • 2
  • 3
  • 4
  • -1

我唯一无法工作的是仅使用入队和出队来反转队列的逻辑，显然我的尝试逻辑完全错误，我被卡住了，因为每个在线页面都只使用一个堆栈但是我不能使用堆栈。

from Queue import Queue

def reverseQueueFirstKElements(k, queue):
    for i in range(k):
        if queue is None:
            return
        temp =  queue.dequeue()
        queue.enqueue(temp)
        node = queue.list.head
        print(node.data)
        

if __name__ == '__main__':
    queue = Queue()
    nums = 0
    k = 0
    while nums != -1:
        nums = int(input())
        if nums == -1:
            break
        else:   
            queue.enqueue(nums)
        k += 1
    node = queue.list.head
    while node is not None:
        print(node.data)
        node = node.next
    reverseQueueFirstKElements(k, queue)

这是队列文件

from Node import Node
from LinkedList import LinkedList

class Queue:
    def __init__(self):
        self.list = LinkedList()
        
    def enqueue(self, new_item):
        # Create a new node to hold the item
        new_node = Node(new_item)
        
        # Insert as list tail (end of queue)
        self.list.append(new_node)
    
    def dequeue(self):
        # Copy data from list's head node (queue's front node)
        dequeued_item = self.list.head.data
        
        # Remove list head
        self.list.remove_after(None)
        
        # Return the dequeued item
        return dequeued_item
4

2 回答 2

0

您不能像尝试那样在循环中执行此操作，因为这不会改变顺序......它只是旋转队列，最终（几乎）与您开始时相同。

这样做的方法是使用堆栈：将队列刷新到堆栈中，然后将堆栈刷新回队列中。

现在，您会说您不应该使用堆栈，但您可以为此目的使用调用堆栈，并使用递归：

def reverse(queue):
    try:
        data = queue.dequeue()
    except AttributeError:
        return queue
    reverse(queue)
    queue.enqueue(data)

请注意，我取消了k，因为无论如何您都希望反转整个队列。

该算法的基本情况是队列为空时。在这种情况下，调用您的dequeue实现将触发访问异常head.data，因为该head成员将None在那个时候。此函数捕获该错误，并返回空队列。然后递归展开，所有值以相反的顺序再次入队。

于 2021-08-10T16:31:56.467 回答
0

我不知道这是否是您要搜索的内容，但 deque 模块具有.reverse()自动反转整个列表顺序的功能。更多信息可以在这里找到：https ://docs.python.org/3/library/collections.html#collections.deque.reverse

于 2021-08-10T10:34:34.217 回答