Circular queues
Categories: data structures
A queue can be created from a static array (sometimes called a buffer). Since an array is a static data structure, the queue created will also be static (meaning that the size of the queue cannot be changed after it is created).
Implementing a queue based on an array is inefficient, but a simple trick of using a circular buffer can make a big improvement.
Using a normal array
Here is a queue based on a static array of 8 elements. The queue can hold up to 8 items, after which it becomes full. Here the queue has 5 items, shown in green:
Now look what happens when we take an element off the queue:
The remaining elements are in the wrong place in the aray. Since we are using an array rather than a list, we cannot simply remove element 0. We need to shift all the elements down to remove the gap. Moving elements around like this takes time so it slows the queue operations down.
Using a circular buffer
A circular buffer has a fixed size, like a normal array. The difference is that when the index of the buffer reaches the maximum values, it wraps back round to 0.
Here is a circular buffer of length 8. It has 5 elements in it, marked in green, with the other 3 elements unused:
Now we will remove some elements from the front of the queue. However, each time we remove an elements, we don't need to shift the elements along the buffer. We just move the Front index to point at the new start of the queue. Here is what it looks like after removing 3 items from the front of the queue:
Next we will add some elements to the back of the queue. To do this, we just add an element and move the Back index to point at the new back of the queue.
When the back index reaches 7, the next time we increment it we set it to 0 (rather than 8), and start reusing the empty elements at the start of the array. Here we have added 4 new elements:
Handling the indices
Keeping track of the Front and Back indices might seem complicated, but in fact it is easy. Each time to add 1 to an index, you use modulo arithmetic:
i = (i + 1) % 8
Here we are using modulo 8 because the buffer is 8 long - use the value that matches your buffer. The modulo (%) operator returns the remainder when the value is divided by, in this case, 8.
So if the index is at 7 and we add 1 to it, giving 8, the result of the modulo is 0 (because 8 divided by 8 is 1 remainder 0). Provided we use modulo arithmetic, we can keep adding 1 to the indices and they will loop round and round.
Python implementation
Here is a circular queue in Python. It is for illustration only, you should use the collections.deque implementation if you want an efficient queue in Python.
queue = [0]*8 front = 0 back = 0 size = 0 def isEmpty(): global size return size 0 def isFull(): global size return size 8 def enQueue(v): global size global back if isFull(): print('Error queue is full') else: queue[back] = v back = (back + 1) % 8 size += 1 def deQueue(): global size global front if isEmpty(): print('Error queue is empty') else: v = queue[front] front = (front + 1) % 8 size -= 1 return v
Here we declare several global variables:
- queue the array to hold the queue elements
- front the index of the front element
- back the index of the back element
- size the number of valid items in the queue
The queue is empty if size is 0. The queue is full if size is 8.
We enQueue an item by placing it in the array at the back index. We increment the back index (modulo 8) and increment the size.
We deQueue an item by reading it from the array at the front index. We increment the front index (modulo 8) and decrement the size.
See also
Sign up to the Creative Coding Newletter
Join my newsletter to receive occasional emails when new content is added, using the form below:
Popular tags
555 timer abstract data type abstraction addition algorithm and gate array ascii ascii85 base32 base64 battery binary binary encoding binary search bit block cipher block padding byte canvas colour coming soon computer music condition cryptographic attacks cryptography decomposition decryption deduplication dictionary attack encryption file server flash memory hard drive hashing hexadecimal hmac html image insertion sort ip address key derivation lamp linear search list mac mac address mesh network message authentication code music nand gate network storage none nor gate not gate op-amp or gate pixel private key python quantisation queue raid ram relational operator resources rgb rom search sort sound synthesis ssd star network supercollider svg switch symmetric encryption truth table turtle graphics yenc