Queue

A queue may be implemented using:

• array - the array would have to be “circular” to keep up with enqueuing/dequeuing items. Without it, we’d have to increase array’s size with enqueue operation taking the last index to infinity.
• linked list - simpler implementation, there is no issue resizing an array.
• two stacks - items are added to one stack. When dequeuing, the all items are moved to another stack, and then read from it.

Reversing

To reverse a queue, we can use a stack. First, we move all items from the queue to a stack. Then, we move all the items from the stack to the queue.