IB Computer Science Topic B2.2.4: Concept of a Queue as a "first In, First Out" (FIFO) Data Structure Notes

Queues: The First Item In Is the First Item Out

1. A queue is a linear data structure that operates on the First In, First Out (FIFO) principle.
2. The first element added is the first one removed, so items are served in the order they arrived.
3. A queue works at both ends: items join at the rear (also called the back) and leave from the front.

The Four Queue Operations

1. enqueue
   1. Adds an element to the rear of the queue.
2. dequeue
   1. Removes the element at the front and returns it, so the queue is one shorter afterwards.
3. front
   1. Returns the element at the front without removing it, so the queue is unchanged.
4. isEmpty
   1. Returns true when there is nothing left, which is what a program checks before calling dequeue or front.

All four operations touch only an end of the queue, so all four run in O(1) time in a well-implemented queue.

Tracing a Queue Step by Step

1. Draw a queue horizontally as a row of boxes, and label which end is the front and which is the rear.
2. Redraw the contents after every operation, and record what each dequeue returned.
3. Getting the ends the wrong way round turns the whole trace into a stack trace and loses every mark, so label them before starting.

Writing a Queue in Java and Python

1. Java has a Queue interface, usually created as a LinkedList, where add is enqueue, remove is dequeue and peek is front.
2. Python has no queue type, so a list is used as one, appending at the end and removing from index 0.

Why pop(0) Is a Slow Way to Dequeue in Python

1. A Python list keeps its elements contiguous and numbered from 0, so removing index 0 forces every remaining element to shift down one place.
2. That makes pop(0) an O(n) operation, which breaks the O(1) promise a queue is supposed to give.
3. The two standard fixes are a linked structure, where dequeuing just moves a pointer, and a circular array, where it just moves an index.

The Circular Queue: Reusing the Space at the Front

1. An array-backed queue keeps two indices: front points at the next item to leave and rear points at the last item added.
2. Dequeuing moves front forward by one instead of shifting the whole array, which is what keeps it O(1).
3. The side effect is that the slots before front become unreachable, so rear can run off the end of the array while the array is not actually full.
4. A circular queue solves this by wrapping the indices back to 0 with the modulo operator.
   1. rear = (rear + 1) % capacity on enqueue.
   2. front = (front + 1) % capacity on dequeue.
5. A full queue and an empty queue leave front and rear in the same relative position, so the implementation also keeps a count of items, or deliberately leaves one slot always empty, to tell the two apart.

Coding a Circular Queue

1. The whole structure is one array, two indices and a count, with no built-in functions needed.
2. Enqueue refuses when count equals capacity, and dequeue refuses when count is 0.

Performance and Memory: Only the Two Ends Are Reachable

1. enqueue, dequeue, front and isEmpty are all O(1) in a linked or circular implementation, because none of them looks past an end.
2. Reaching an item in the middle costs O(n), because everything in front of it has to be dequeued first.
3. An array-backed queue is static: it has a maximum length, so enqueuing onto a full queue causes queue overflow, and unused slots stay reserved.
4. A linked or list-backed queue is dynamic: it has no fixed ceiling, but it pays for that in resizing or in a pointer per item.

Choosing a Queue for a Scenario

1. A circular array queue
   1. Fits a printer buffer that holds at most 20 jobs, where the ceiling is known and the memory budget is fixed.
2. A dynamic queue
   1. Fits a web server holding incoming requests, where the number arriving in a second cannot be predicted and refusing a request is worse than using more memory.
3. A plain static array queue
   1. Rarely the right choice, because the wasted front slots make it worse than the circular version for no saving.

Where Queues Show Up

1. Task scheduling
   1. An operating system holds ready processes in a queue, and round robin scheduling dequeues one, runs it for a time slice, then enqueues it again at the rear.
2. Networking
   1. A router holds arriving packets in a buffer queue and forwards them in arrival order, and when the buffer fills, later packets are dropped.
3. Print spooling and keyboard buffers
   1. Both hold input that arrives faster than it can be dealt with, and both have to release it in the order it arrived.
4. Simulations
   1. Modelling a checkout line or a call centre means enqueuing arrivals and dequeuing them as servers become free, so the average wait can be measured.
5. Breadth-first search
   1. Exploring a network one step at a time works by enqueuing every neighbour, which is what makes the search spread outwards evenly rather than diving down one path.