Using Stacks In Queues

To create a queue using two stacks, we use two main stacks: one (stack1) for adding new items and the other (stack2) for removing items in the correct order. Here's how it works step by step:

1. Adding Items (Enqueue):
   When we want to add an item to the queue, we always push it onto stack1. This is quick and easy because we don't have to worry about the order at this stage.

2. Removing Items (Dequeue):

   • When we want to remove an item, the item at the front of the queue needs to be removed first (FIFO). However, since stack1 is a stack, the last item added is on top.

   • To fix this, we move all the items from stack1 to stack2. This reverses their order so that the oldest item (the first one added) is now on top of stack2.

   • We then pop the top item from stack2, which represents the front of the queue.

3. How It Works Together:

   • If stack2 already has items, we don't need to transfer anything from stack1—we can directly pop from stack2.

   • If stack2 is empty, we move all the items from stack1 to stack2, ensuring the queue's order is correct.