The Two Stacks (s1 & s2)
Stack `s1` is used for incoming elements. Stack `s2` is used for outgoing elements. Because stacks reverse order, moving data from `s1` to `s2` flips it back into FIFO order.
Loading...
Loading...
Loading Curriculum...
Loading Subject...
Loading Topic...
Loading Lesson...
Loading Lab...
How can you mimic the First-In-First-Out (FIFO) behavior of a Queue using only Last-In-First-Out (LIFO) Stacks? You need exactly two stacks to reverse the order twice.
Stack `s1` is used for incoming elements. Stack `s2` is used for outgoing elements. Because stacks reverse order, moving data from `s1` to `s2` flips it back into FIFO order.
Pushing is extremely simple. Just `s1.push(x)`. That's it. It takes O(1) time.
If `s2` is not empty, simply `s2.pop()`. If `s2` IS empty, you must pop EVERY element out of `s1` and push them into `s2`. This reverses the entire sequence, placing the oldest element at the top of `s2`. Then pop from `s2`.