Interview Question

Interview(Student Candidate) Seattle, WA

Create a Queue using two Stacks.

data structures

Interview Answer

2 Answers


There was no coding required, only showing/drawing how it would work and describe its algorithmic complexity.

Interview Candidate on Mar 29, 2012

The solution uses two operation swap() which swaps the top elements in both stacks move(0 or 1) if it's 0 them moves top item from stack 0 to stack 1 and vice versa Given stack S0 and S1 move(0)= push(S1, pop(S0)) swap() = x = pop(S0) push(S0,pop(S1)) push(S1,x) So the solution is to repeat swap and move. By induction, a 1 item stack is already a queue. Given this works for i, here is how it would work for i+1 (to make this example simple I will show it for i=4) Since it works for 4 then you have the following stacks: S0 S1 e1 e2 e3 e4 (push new element into S0) S0 S1 e5 e1 e2 e3 e4 (move) S0 S1 e1 e5 e2 e3 e4 (swap) S0 S1 e5 e1 e2 e3 e4 (move) S0 S1 e2 e5 e3 e1 e4 (swap) S0 S1 e5 e2 e3 e1 e4 (move) S0 S1 e3 e5 e4 e2 e1 (swap) S0 S1 e5 e3 e4 e2 e1 (move) S0 S1 e4 e5 e3 e2 e1 (swap) e5 e4 e3 e2 e1 (move, move, move, move) S0 S1 e1 e2 e3 e4 e5

Swap/Move on Aug 23, 2012

Add Answers or Comments

To comment on this, Sign In or Sign Up.