Reverse a Queue in Python
In this tutorial, we will learn the different techniques used to reverse a Queue in Python. The queue is a data structure the supports first-in-first-out ( FIFO ) semantics for inserting and deleting elements. The Insert operation is also called as enqueue and delete operation as dequeue. We can reverse a queue using two methods in Python.
- Using Stack.
- Using Recursion.
Reverse a Queue using Stack in Python
Stack follows the last-in-first-out( LIFO ) principle. Similar to the Queue, the insert operation is called push and remove operation as pop. In this method, we will dequeue the elements from the Queue and push them into the Stack. Until the Queue becomes empty. Then we pop the elements from the Stack and enqueue them to the Queue till the stack is empty. As a result, the elements in the Queue will be reversed.
The elements should be added to the Rear and removed from the Front in a queue.
class Stack: def __init__(node): node.data = [] def Empty(node): return node.data == [] def push(node, data): node.data.append(data) def pop(node): return node.data.pop() class Queue: def __init__(node): node.data = [] def Empty(node): return node.data == [] def enQueue(node, data): node.data.insert(0,data) def deQueue(node): return node.data.pop() def Reverse(): while( not Q.Empty()): S.push(Q.deQueue()) while( not S.Empty()): Q.enQueue(S.pop()) S = Stack() Q = Queue() Q.enQueue(5) Q.enQueue(4) Q.enQueue(3) Q.enQueue(2) Q.enQueue(1) print(Q.data) Reverse() print(Q.data)
Output:
[1, 2, 3, 4, 5] [5, 4, 3, 2, 1]
Reverse a Queue using Recursion
In recursion, a function calls itself either directly or indirectly as a subroutine. As a result, it requires less amount of code to perform the necessary tasks. Hence, considered one of the efficient methods in programming. While writing a recursive function, we must keep in mind that it should have a base case and the algorithm must change its state and move towards the base case.
class Queue: def __init__(node): node.data = [] def Empty(node): return node.data == [] def enQueue(node, data): node.data.insert(0,data) def deQueue(node): return node.data.pop() def Reverse(): if(Q.Empty()): return temp = Q.data[-1] Q.deQueue() Reverse() Q.enQueue(temp) Q = Queue() Q.enQueue(5) Q.enQueue(4) Q.enQueue(3) Q.enQueue(2) Q.enQueue(1) print(Q.data) Reverse() print(Q.data)
Output:
[1, 2, 3, 4, 5]
[5, 4, 3, 2, 1]
I hope you understood the code..!
You can also read more about Recursion and Stack here.
If you have any quires, please feel free to drop in your comments.
Thank you…🙂
Leave a Reply