How do you implement a queue using two stacks?

You can implement a queue using two stacks by pushing elements into one stack and popping them from the other.

A queue is a data structure that follows the First-In-First-Out (FIFO) principle, where the first element that is added is the first one to be removed. On the other hand, a stack is a data structure that follows the Last-In-First-Out (LIFO) principle, where the last element added is the first one to be removed. To implement a queue using two stacks, we need to cleverly manipulate these two stacks to follow the FIFO principle.

Let's call the two stacks as 'inputStack' and 'outputStack'. When we want to add (enqueue) an element into the queue, we simply push it into the 'inputStack'. This operation has a time complexity of O(1), which means it is a constant time operation, regardless of the number of elements in the stack.

When we want to remove (dequeue) an element from the queue, we pop an element from the 'outputStack'. If the 'outputStack' is empty, we pop all elements from the 'inputStack' and push them into the 'outputStack' one by one. This way, the last element added into the 'inputStack' (which is the first one to be removed in a queue) becomes the top element in the 'outputStack' and can be popped out following the FIFO principle. This operation has a time complexity of O(n), where n is the number of elements in the 'inputStack'.

It's important to note that the time complexity of the dequeue operation is O(n) only when the 'outputStack' is empty. If the 'outputStack' already has elements, the dequeue operation also has a time complexity of O(1). Therefore, the amortised time complexity (average time over all operations) of both enqueue and dequeue operations is O(1), which makes this implementation efficient.

In summary, by using two stacks, we can implement a queue where the enqueue operation is performed on one stack and the dequeue operation is performed on the other stack. This clever use of stacks allows us to maintain the FIFO principle of a queue.