Assignment 2 is writing a linked list to implement a queue
Queues are sometimes referred to as "fair algorithms" (although prof dislikes)
FIFO (first in, first out)
For a print queue, want a request class (data) and a collection class (the data structure)
Items are inserted at back and removed from front, like a line. Or a queue.
Queues need to implement at least insert (enqueue) and remove (dequeue). Peek is optionally but very
nice to have! And, of course, default constructor that allows you to create an empty queue.
Assumed that these will be performed efficiently, in constant time
Dequeue is just dependant on order in which elements are recieved, nothing else.
Will be looking at two implementations: one with an array, one with a linked list
What is the index going to be for the front and the back of the queue?
Back -> current size of array, much like stack implementation
Initially make front of queue index 0.
Inserting is easy!Add and increment back.
Removing: remove and increment front. Don't reuse the space at the front. Wastes space. Could have
absurd situation where queue is full, but only has 1 entity in it.
Could go and shuffle everything down rather than incrementing front. However, this is not constant
So, can use a circular array. Not a new data structure; just pretend that it's arranged in a circle, rather
than a straight line. End of array wraps around and fills empty spaces in front.
Mod operator (%) calculates remainders.
Can be used to calc front and back in circular array without if statements!
Back of queue is: (front + num) % queue.length
num is number of items in queue
After removing an item the front of the queue is:
(front + 1) % queue.length;
If you're going to make a bigger array, could fill new array from index 0 upwards, but start at the actual
front. So, in the new array front of the new queue is 0.A bit less confusing/hard to map this way! In the
end, all that matters are that items are in the same order and the front and back indices are correct. Can
implement in multiple ways!
However, isn't always be better to have so