Microsoft interview question
In any language you want, write a queue using only stacks.
Interview Answer
Anonymous
30 Mar 2025
Create 2 stacks. On "append" add to the first one. On "remove" remove from the second one, unless it is empty, in which case move all items from the first stack to the second (flipping their order) and then remove from the second one. This keeps the amortized complexity identical to a regular queue.