Amazon Interview Question: Create a Queue using two Stac... | Glassdoor

## Interview Question

Software Development Engineer 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