Queue using stacks & stack using queues

Buddhini Abayaratna — Thu, 22 Aug 2019 18:40:59 +0000

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:

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

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

STEP 1 :

pop elements from stack 1 and push into stack 2 until stack 1 is empty.

STEP 2 :

Now, push the element to be enqueued into stack 1

STEP 3 :

And then, pop elements from stack 2 and push them back to stack 1 until stack 2 is empty.

STEP 4 :

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:

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

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

STEP 1:

Enqueue the element to be pushed into queue 2.

STEP 2:

One by one, dequeue elements from queue 1 and enqueue them into queue 2.

STEP 3:

Now, simply swap the name of the two queues.

STEP 4:

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:

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.

DEV Community: Buddhini Abayaratna