### Data structure problem 1:Implement a queue using 2 stacks.

This is one of the interview questions asked in technical or data structure round.

As we know **stack is first in last out** and **queue is first in first out.**

Here we have to implement the behaviour of queue using 2 stacks.

So let's begin with one of the approaches,

For 2 stacks we have define 2 arrays;

var stack1=[];

var stack2=[];

For insertion or push, we will use stack1.

For any insertion, we can push it in stack1 array.

**a)Insert "A"**

stack1.push("A");

**b)Insert "B"**

stack1.push("B");

**c)Insert "C"**

stack1.push("C");

Now when we remove or pop, the first pushed element should be removed first i.e behaviour of a queue.

So if we poped from stack1 we will get the behaviour of stack here.

stack1.pop()//"C" will be removed i.e behaviour of stack last in first out.

**We can't use this, so we will need stack2 for this purpose to implement the behaviour of the queue.**

**d)Remove or pop:**

For **first remove or pop,** we will need to pop every element in stack1 and push it to stack2.

So here are the values of stack2 and stack1,

** stack2 =["C","B","A"];**

** stack1=[];**

**And then pop from stack2. **

i.e stack2.pop()//"A" will be poped which is inserted first.

**So here we have implemented behaviour of queue.**

**For another insertion or push,**

**e)Insert "D"**

stack1.push("D");

**stack1=["D"];**

**stack2=["C","B"];**

**Now for 2nd remove operation first we need to check if stack2 is empty. **

**If not empty then just pop element from stack2 for every remove**

**operation till stack2 becomes empty.**

stack2.pop()//=>"B"

stack2.pop()//=>"C"

Now stack 2 is empty, So we can't pop .

**stack1=["D"];**

**stack2=[];**

**So if stack2 is empty then pushed all elements from stack1 to stack2 and pop stack2.**

**i.e one that we had done for first remove or pop operation.**

**stack1=[];**

**stack2=["D"];**

stack2.pop()//=>"D"

**By this approach, we can implement a queue using two stacks.**

I hope you like this article. Please stay connected for more such articles.

If any doubts please let me know in the comment section.

You can also follow me on **Twitter** or **Linkedin **for** **the** **latest updates.

**Saurabh Joshi**

## Comments

## Post a Comment