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

Question

hummedfelon · Accepted Answer

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

blakdogg · Answer

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.

Utilisateur anonyme · Answer

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.

Utilisateur anonyme · Answer

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.

Mahdi · Answer

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;
}

Jegan · Answer

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

Google

Question d’entretien chez Google

Réponses aux questions d'entretien

Entreprises suivies

Recherche d’emplois