CP164 Study Guide - Midterm Guide: Circular Buffer, Init
The Circular Array-Based Queue
When an item is removed from the front of the queue, the value of the index front must be
changed. If front is a value from 0 to n-1, it gets changed to front+1. If front is n-1, it gets
changed to 0. That is easy to do with the modulus operator:
front = (front + 1) % n
The value of rear is handled in a similar manner.
Note that rear refers to the index of the next available slot in the array, not the index of the
last item in the queue. Thus when the circular queue is empty, both front and rear refer to
the same slot in the array. However, when the queue is full, both front and rear refer to
the same slot in the array. How, then, can we tell the difference between when the queue is
full and when the queue is empty? (This is left as an exercise to you.)
Circular Queue Methods
These queue differ slightly from the standard queue methods as noted:
• initialize: create an empty queue
• insert: adds a new value to the rear of the queue - fails if the queue is full. (Returns True if
the insertion is successful, False if the insertion fails.)
• remove: removes and returns the value in the front of the queue, if one exists, and returns a
null value otherwise
• peek: return a copy of the value at the front of the queue without removing it, if one exists,
and returns a null value otherwise
• is empty: returns True if the queue is empty, False otherwise
• is full: returns True if the queue is full, False otherwise
• length: returns the number of items in the queue - not the fixed length of the value array
Circular Queue Implementation
Given that Python's list is dynamic, how can we create a fixed size array from it? We can do
so quite simply by filling it with place holders when we create it and never changing the
size of the list (i.e. by never calling pop or append on it) in any of the Circular Queue
methods. The initialization would be:
class Queue:
def __init__(self, max_size):
"""
-------------------------------------------------------
Initializes an empty queue. Data is stored in a fixed-size list.
Use: cq = Queue(max_size)
find more resources at oneclass.com
find more resources at oneclass.com
Document Summary
When an item is removed from the front of the queue, the value of the index front must be changed. If front is a value from 0 to n-1, it gets changed to front+1. If front is n-1, it gets changed to 0. That is easy to do with the modulus operator: front = (front + 1) % n. The value of rear is handled in a similar manner. Note that rear refers to the index of the next available slot in the array, not the index of the last item in the queue. Thus when the circular queue is empty, both front and rear refer to the same slot in the array. However, when the queue is full, both front and rear refer to the same slot in the array. How, then, can we tell the difference between when the queue is full and when the queue is empty? (this is left as an exercise to you. )
