Ran across a question on how to implement a stack by only using queues on SO, so I decided to give it a go in Java and PHP. It’s actually pretty straight forward:
- Initialize two queues.
- On every push operation, if both queues are empty, add to the first queue.
- If one of the queues is full (one will always be empty), pop off all the elements from the full queue and add them to the empty queue in the same order (as they were popped). This guarantees the full queue will always be sorted like a stack, so when a pop occurs, it is popped in the “LIFO” order, not “FIFO” order.
Code after the break. Continue reading