Queues
We know Queues well from IC211. If a Stack is a LIFO (Last-In First-Out), then a Queue is a FIFO (First-In First-Out). In other words, things come out in exactly the same order they went in.
Think about a line for the checkout counter at the grocery store (after all, "queue" is British for "line"). People can only join the line at the end, and only leave the line at the front. In between, they never switch order.
The methods a Queue must have are:
- enqueue(e) - Add an element to the back of the Queue
- dequeue() - Remove and return the front element of the Queue
- head() - Return, but do not remove, the front element of the Queue
Implementation
Implementation with a Linked List is fairly straightforward. Enqueue is just an add-to-back, which is O(1) if we have a pointer to the last link in the Linked List. Dequeue is just a remove-from-front, which, again, is O(1). head is Dequeue but easier, so it is also O(1).
Implementation with an array requires a bit more bookkeeping. Every time we dequeue, we don't want to shift everything down so that the first element remains at the front of the array, that would be expensive and silly. So, we keep two values: front, and size. Front the index of the first element of the queue, and size indicates the number of elements in the queue. As elements are enqueued and dequeued, the queue can wrap around the end of the array, back to the beginning of the array if appropriate. If the array fills up, we double the size of the array, as with the stack. So, enqueue is an AMORTIZED O(1), just like push. dequeue and head are also trivially O(1).
So, we resize our array when size==array length. Aside from that, how do we do find the index of the first open space, when we're allowed to wrap around? Well, if our array was infinitely long, or no wrapping was required, the first open index would be at front+size. Since we're wrapping, it's at (front+size)%array.length. After inserting your element, you then have to increment size.
To dequeue, we want to indicate that the element currently at index "front" is now eligible for a new element. So, we increment front (wrapping back around to 0 if need be), and decrement size.