Stack with an REVERSE Operation
Implementation of a queue using (Stack + Reverse)
Stack is a linear data structure which follows a particular order in which the operations are performed. The order may be LIFO(Last In First Out) or FILO(First In Last Out). Read More
Queue is a linear structure which follows a particular order in which the operations are performed. The order is First In First Out (FIFO). Read More
Now, let us consider an implementation of stack in which along with PUSH and POP operations it also supports an operation to REVERSE the orders of element on the stack.
For queue we require to insert the new element at the rear end and delete the element from front end while in stack we do both the operations (insert and delete) from only one end.
To simulate the queue using such stack, we need to perform the ENQUEUE and DEQUEUE operations using supported stack operations (PUSH, POP and, REVERSE).
Let us consider an example:
We have following elements to insert in the queue using stack:
10, 15, 20, 30
ENQUEUE
Intially the stack is empty, so we will directly push the first element 10 onto the stack:
Now while inserting the elements we will perform ENQUEUE using PUSH and REVERSE operation:
1. Reverse the Stack
2. Push the element
3. Again, Reverse the Stack
Now Lets Add 20:
1. Reverse the Stack
2. Push the element
3. Reverse the stack
Now Lets Add 20:
1. Reverse the Stack
2. Push the element
3. Reverse the element
So, we have successfully en-queued the elements using the 3 successive stack operations:
1. REVERSE
2. PUSH
3. REVERSE
DEQUEUE
For performing DEQUEUE, we can simply POP the element as we have already reversed the stack in the ENQUEUE, due to which the first inserted element always remains on the top of the stack.
