Implement a queue using 2 stacks

Use 2 stacks, S and T

1. Enqueue
S.push()

2. Dequeue
if T.count==0
while (S.count>0) t.push(s.pop());

T.pop();

The operations take O(1) amortized time.

Reference
C SC 545 Exam Fall 08