Stack with an REVERSE Operation

Implementation of a queue using (Stack + Reverse)

Photo by Mathieu Turle on Unsplash

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

Stack after Reverse operation (since here there is only one element so the stack will look like the same)

2. Push the element

Stack after Push (15) operation

3. Again, Reverse the Stack

Stack after Reverse operation

Now Lets Add 20:

1. Reverse the Stack

Stack after Reverse operation

2. Push the element

Stack after Push (20) operation

3. Reverse the stack

Stack after Reverse operation

Now Lets Add 20:

1. Reverse the Stack

Stack after Reverse operation

2. Push the element

Stack after Push (30) operation

3. Reverse the element

Stack after Reverse operation

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.

10 (First inserted element is on the top)

--

--

Pursuing M. Tech in Computer Science at IISc, Bangalore | Machine Learning Enthusiast

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Ashish Kankal

Pursuing M. Tech in Computer Science at IISc, Bangalore | Machine Learning Enthusiast