CITS2200 - Lecture 12

← Back to Home

CITS2200 - Lecture 11
Queues - Slides

The Queue ADT

• Queue stores arbitrary objects using FIFO (first-in, first-out)
  • Stack = LIFO
  • Queue = FIFO
• Insertions at the rear, removals at the front

Operations:

• enqueue(e) → insert at rear
• dequeue() → remove + return from front
• first() → peek front (no removal)
• len() → return number of elements
• is_empty() → return Boolean to indicate if queue is empty

Exceptions:

• Throws EmptyQueueException if dequeue/first on empty queue

Array-Based Implementation

Uses circular array of size $N$ with modulo arithmetic:

• Variables: $f$ (front index), $r$ (index past rear) $-$ $r$ is kept empty

Circular Arrays

• Shifting every item left when you dequeue → slow and inefficient
  • Instead, just move the front (f) pointer forward
• When your f or r pointer hit the end of the array, they wrap back around to index 0

Operation Implementation:

• size() = (N - f + r) mod N
• enqueue: place at Q[r], then r = (r + 1) mod N
• dequeue: grab Q[f], then f = (f + 1) mod N

Doubles capacity when full → $O(1)$ amortized

Python Queue Implementation

Use of ArrayQueue class with three instance variables:

• _data (the underlying list)
• _size (how many elements are in it)
• _front (index of the first element)

When the array is full → double capacity using the same doubling strategy as dynamic arrays seen in lecture 8

Note: no need for dedicated rear pointer, next available space is given by:

r = (self._front + self.size) % len(self._data)

All operations are $O(1)$ amortized

Round-Robin Scheduler

• Each process gets a turn, then re-joins the back of the queue:
  1. e = Q.dequeue()
  2. Service e
  3. Q.enqueue(e)
• Each process gets a fair turn, cycling indefinitely

---

CITS2200 - Lecture 13