Queue using stacks & stack using queues
Tags: queue, stack, interview
Published: 2019-08-22 18:40:59

---
title: Queue using stacks & stack using queues
published: true
description: 
tags: #queue #stack #interview
cover_image : https://thepracticaldev.s3.amazonaws.com/i/3wwimuhnzdg96chz25a8.png
---

#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](https://thepracticaldev.s3.amazonaws.com/i/socv0kv20ymmfiwsrdid.png)

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](https://thepracticaldev.s3.amazonaws.com/i/er70jjsesvaf3ri24ikg.png)
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](https://thepracticaldev.s3.amazonaws.com/i/imi0y32tkndb0a9eg5ag.png)
pop elements from stack 1 and push into stack 2 until stack 1 is empty.

**STEP 2 :**
![Alt Text](https://thepracticaldev.s3.amazonaws.com/i/t9dsfzzsptbid85q9ht2.png)
Now, push the element to be enqueued into stack 1

**STEP 3 :**
![Alt Text](https://thepracticaldev.s3.amazonaws.com/i/6bkk2chny8ck7g8olcmj.png)
And then, pop elements from stack 2 and push them back to stack 1 until stack 2 is empty.

**STEP 4 :**
![Alt Text](https://thepracticaldev.s3.amazonaws.com/i/nuauuv68sumlia9ex7fh.png)
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](https://thepracticaldev.s3.amazonaws.com/i/3p6qxt2037mzre49mabm.png)
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](https://thepracticaldev.s3.amazonaws.com/i/copwplt9rs4jnbr23jp0.png)
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](https://thepracticaldev.s3.amazonaws.com/i/11vtho0r14ef9mlfm8to.png)
Enqueue the element to be pushed into queue 2.

**STEP 2:**
![Alt Text](https://thepracticaldev.s3.amazonaws.com/i/1dpbtdg4b63t3agjjxt6.png)
One by one, dequeue elements from queue 1 and enqueue them into queue 2.

**STEP 3:**
![Alt Text](https://thepracticaldev.s3.amazonaws.com/i/slwmdasmhirzuzkcwtcl.png)
Now, simply swap the name of the two queues.

**STEP 4:**
![Alt Text](https://thepracticaldev.s3.amazonaws.com/i/n0j9335ydz0gb6sr0mnf.png)
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](https://thepracticaldev.s3.amazonaws.com/i/kvvnq4baefuozndrd7s4.png)
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!:tada:
And you are one step closer to impress your interviewer.