A few years ago, during a job interview for Google, a friend got the following challenge: “implement a queue using two stacks”. I found it an interesting challenge, so I decided to give it a thought (for the inverse problem, check the next post). Before you keep reading, think about how you would approach this challenge.
… Done?
Let’s begin with a brief review on stacks and queues.
Stacks and queues A stack is a collection of elements based on the concept of Last In First Out (LIFO): the last added element is the first to leave.