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.