Interview Question

Software Engineer Intern Interview

-Sydney

Google

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

Answer

Interview Answers

7 Answers

0

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

0

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

1

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

0

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

0

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

0

Please check my videos that explain "How to implement a queue from two stacks?" Part 1 - https://www.youtube.com/watch?v=_PIRZqC0pS0 Part 2 - https://www.youtube.com/watch?v=D2Z2iGQW7cM Part 3 - https://www.youtube.com/watch?v=DeChmB6JSZw

Jegan on

0

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 http://www.algoqueue.com/algoqueue/default/view/7733248/queue-using-stack

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.