DEV Community

loading...
Cover image for Queue using stacks & stack using queues

Queue using stacks & stack using queues

jellybee profile image Buddhini Abayaratna Updated on ・3 min read

Stack and Queue: What ❔

Both are non-primitive, linear data structures. The main difference among two is that the stack uses LIFO (Last-in First-out) access policy whereas the queue uses FIFO (First-in First-out) access policy.

To quickly demonstrate the two data structures:

Alt Text

In this post, we're not gonna dig deep into the implementation of the two data structures. Instead, we will talk about a very common interview question for computer science / software engineering graduates.

Q : How to implement a queue using stacks and a stack using queues?😮

Worry not, it's peanuts!🙃
As you know, for both data structures there're two main operations we consider about. INSERTION and DELETION
In other terms, for stack it should be push and pop while for queue it's enqueue and dequeue.
Let's go through one at a time..

Queue using stacks (actually two)

ENQUEUE

Alt Text
So we have a queue which has correctly enqueued 1 , 2 elements and now we wish to add 3 into it.

STEP 1 :
Alt Text
pop elements from stack 1 and push into stack 2 until stack 1 is empty.

STEP 2 :
Alt Text
Now, push the element to be enqueued into stack 1

STEP 3 :
Alt Text
And then, pop elements from stack 2 and push them back to stack 1 until stack 2 is empty.

STEP 4 :
Alt Text
There you go!

DEQUEUE

STEP 1 :
First, we need to check whether stack 1 is empty (which in our case is not). If so, an error message should be displayed 'Underflow'. Because there's no element to throw away.

STEP 2:
Alt Text
pop an element from stack 1 and return it.

Note to consider: we made the enqueue algorithm expensive here. Which means, we did the hard work for enqueue and dequeue was just popping up the top element. You can try it yourself making the dequeue algorithm costly.

Stack using queues (again two)

PUSH

Alt Text
So we have a stack which has correctly pushed 1 , 2 elements and now we have to push 3 into it.

STEP 1:
Alt Text
Enqueue the element to be pushed into queue 2.

STEP 2:
Alt Text
One by one, dequeue elements from queue 1 and enqueue them into queue 2.

STEP 3:
Alt Text
Now, simply swap the name of the two queues.

STEP 4:
Alt Text
That's it!

Another Approach: Check out @mvthanoshan 's take on this..
https://dev.to/mvthanoshan/comment/19hpc

POP

STEP 1:
Check whether both queues are empty. If so, it should alert 'Underflow'.

STEP 2:
Alt Text
dequeue an element from queue 1 and return it.

Note to consider: here as well we made the insertion method, pushing expensive. You may try the vice versa for your practice.

Tada!🎉
And you are one step closer to impress your interviewer.

Discussion (3)

pic
Editor guide
Collapse
mvthanoshan profile image
Thanoshan MV

Hi, in creating Stack using two Queues, when we want to insert 3 to queue1, what if:

  1. dequeue all elements from queue1 and enqueue them to queue2
  2. enqueue 3 to queue1
  3. dequeue all from queue2 and finally enqueue them into queue1

Instead of swapping name of two queues, can't we do like the above in the insertion operation?

Collapse
jellybee profile image
Buddhini Abayaratna Author

Hi Thanoshan!
Yes!! That's another take on the operation and as I checked, far more efficient when taking elapsed time into account.
I made an edit to the post, so that others can look into your opinion🤠
Thanks for sharing your thoughts!

Collapse
mvthanoshan profile image
Thanoshan MV

Thanks! Do share more articles related to Data Structures.