Amazon.com

www.amazon.com
Engaged Employer

## Interview Question

Interview(Student Candidate) Seattle, WA

# Create a Queue using two Stacks.

Tags:
data structures

1

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

Interview Candidate on Mar 29, 2012
0

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