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

Queue using stacks & stack using queues

jellybee profile image Buddhini Abayaratna ・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!

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.

Posted on by:

jellybee profile

Buddhini Abayaratna

@jellybee

Undergraduate ▪️ Designer ▪️ Saltwaterheart

Discussion

markdown guide