pythonqueueenqueue

Reversing a queue only using enqueue and dequeue


for example the input may be

the only thing I cannot get working is the logic around reversing the queue only using enqueue and dequeue and obviously my attempt logic is completely wrong, I'm stuck as every online page just uses a stack however I cannot use a stack.

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)

here is the Queue file

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

Solution

  • You cannot do this in a loop as you tried, because this just does not change the order... it just rotates the queue only to end up (almost) the same as you started.

    The way to do this, is using a stack: flush the queue unto a stack, and then flush the stack back into the queue.

    Now, you'll say you are not supposed to use a stack, but you can use the call stack for this purpose, and use recursion:

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

    Note that I did away with k, since you want anyway to reverse the whole queue.

    The base case of this algorithm is when the queue is empty. In that case calling your dequeue implementation will trigger an exception on accessing head.data, since the head member will be None at that time. This function traps that error, and returns the empty queue. Then the recursion unwinds, and all values get enqueued again in opposite order.