Interview Question

Software Engineer Intern Interview



How to implement a queue simply using two stacks and how to implement a highly efficient queue using two stacks.


Interview Answers

7 Answers


Declare two stacks called in and out. queue.insert() calls in.push() queue.remove() if (out.notEmpty) out.pop() else { while(in.notEmpty) out.push(in.pop) } Don't get how this would be two questions.

blakdogg on


Because that is the simple implementation, pretty much the exact same answer I gave them, there apparently is a more efficient way of modelling it.

Anonymous on


Queue should implement FIFO. Let's have a group of task 1 -10 to be performed //declare two stacks Stack S1, S2; //feed stack S1 with the tasks 1 - 10 for(int i=1; i<=10;i++) { S1.push(i); } //Now S1 contains {10,9,8,7,6,5,4,3,2,1} where the top is 10 //Transfer all from S1 to S2 while(!S1.isEmpty()) { S2.push(S1.pop()); } //Now S2 contains {1,2,3,4,5,6,7,8,9,10} where the top is 1 You can now pop tasks from S2. Task 1 will be the first to pop and so on... Therefore, you just simulated FIFO using two stacks

hummedfelon on


blakdogg's answer is efficient, and has amortized time O(n). The trick here is that when you enqueue an element, you only push into one stack. Only move element when dequeue. Otherwise, running time will be more than O(n). Details are in CLRS amortized analysis.

Anonymous on


template class Q{ private Stack S1,S2; public Q(); ~Q(); void enQ(item *); item* dQ(); int empty(); } void Q::enQ(item * i){ if(S1.empty&&~S2.empty) while(~S2.empty) S1.push(S2.pop()); S1.push(i); return; } item Q::dQ(){ if(S2.empty&&~S1.empty) while(~S1.empty) S2.push(S1.pop()); return S2.empty?0:S2.pop; } int Q::empty(){ return S1.empty()&&S2.empty; } Q::Q(){ S1=new Stack; S2=new Stack; } Q::~Q(){ delete S1; delete S2; }

Mahdi on


Please check my videos that explain "How to implement a queue from two stacks?" Part 1 - Part 2 - Part 3 -

Jegan on


Enqueue : Push elements to stack1. Dequeue : If stack2 is not empty, pop elements from stack2. Otherwise, pop elements from stack1 and push them to stack2 first. Then, pop elements from stack2. For explanation, example and code

Lal on

One or more comments have been removed.
Please see our Community Guidelines or Terms of Service for more information.

Add Answers or Comments

To comment on this, Sign In or Sign Up.