Circular Queue or Ring Buffer

Python and C Implementation.

Introduction

There are many different implementations of the circular queue all of which may be better suited for specific applications. This blog post is to help understand how a circular queue works along with its uses and advantages.

Circular Queue

A Queue is a simple data structure that implements the FIFO (First-In-First-Out) ordering. This simply means that the first item added to your queue is the first one out. Just like a line or queue of customers at the deli, the first customer in line is the first to be served. A circular queue is essentially a queue with a maximum size or capacity which will continue to loop back over itself in a circular motion.

Applications

Ring Buffers are common data structures frequently used when the input and output to a data stream occur at different rates.

• Buffering Data Streams
• Computer Controlled Trafficking signal systems
• Memory Management
• CPU scheduling

Advantages

Circular Queues offer a quick and clean way to store FIFO data with a maximum size.

• Doesn’t use dynamic memory → No memory leaks
• Conserves memory as we only store up to our capacity (opposed to a queue which could continue to grow if input outpaces output.)
• Simple Implementation → easy to trust and test
• Never has to reorganize / copy data around
• All operations occur in constant time O(1)

Disadvantages

Circular Queues can only store the pre-determined maximum number of elements.

• Have to know the max size beforehand

How Does it Work? (Array Implementation)

There are two primary operations on a circular Queue :

1: Enqueue(item) : add item to the Queue.

if Queue.isfull()
    print "Queue is Full"
else 
    increase tail by 1
    Queue[tail] = item
    size++

2: Dequeue(): return the item at the front (head) of the line and remove it.

if Queue.isEmpty()
    print "Queue is Empty"
else 
    tmp = Queue[head]
    increase head by 1
    size--
    return tmp

Note: We aren’t actually removing anything from the array, we are just increasing the head to point at the next item “in line”.

Let’s take a Look at how these operations look on an Array of size 6:

• Notice how the tail wraps back around to zero as we enqueue our seventh item (35).
• Notice how the head increases as we dequeue, but no values are removed from the array, they are only over-written as Enqueue( ) reaches that location in the array.

The Modulo Operator

If we’re supposed to be increasing the head and the tail by 1 spot in the array how do we set it back to zero when we get to the end to ensure we keep looping through the array?

We could do something like this:

if (head + 1) = capacity 
    head = 0
else 
    head = head + 1

There's really nothing wrong with that, however, there’s a much more elegant method using the modulo operator. The modulo operator (%) gives the remainder after division. When looking at the relationship between two integers a and b; a will be the product of b times some integer q plus some integer r :

a = b x q + r
    q : quotient = a div b
    r : remainder = a mod b

Let’s look at some quick examples:

a = b x q + r                    a % b = r
5 = 3 x 1 + 2                    5 % 3 = 2
2 = 5 x 0 + 2                    2 % 5 = 2
9 = 3 x 3 + 0                    9 % 3 = 0
9 = 2 X 4 + 1                    9 % 2 = 1

Note: This is the basis of Euclid’s Algorithm for determining GCD.

Let's apply it to our circular queue implementation:

self.head = (self.head + 1) % self.capacity

• Now every time we get to the end of the array we will automatically start back at zero. Beautiful! Let’s see what this would look like with a circular queue of size 6 :

0 % 6 = 0
1 % 6 = 1
2 % 6 = 2
3 % 6 = 3
4 % 6 = 4
5 % 6 = 5
6 % 6 = 0
...

Python Implementation

This is a simple implementation where we only have the two primary methods, Enqueue(item), Dequeue( ), as well as a display( ) method which I think is helpful in understanding. Many other implementations might also include :

• isFull( ): true if queue is full, false otherwise.
• isEmpty( ): true if queue is empty, false otherwise.
• peek( ) : see what is at the head of the queue without “removing” it.
• etc..

Many other implementations won’t store the current size and will determine isFull( ) and isEmpty( ) by simply comparing the head and tail. I think storing the size makes it easier to follow exactly what is going on.

C Implementation

You can see the C implementation is very similar to the Python implementation with the addition of the fun C stuff like structs and memory allocation. Here we also need a create_queue( ) function as we are using structs. We also use some helper functions that we talked about earlier like isFull( ), isEmpty( ), etc..

Thinkers

• What are some boundary cases?
• What assumptions are we making?
• How would we implement the circular queue to have the ability to change capacity on the fly? How would this affect our advantages and disadvantages of the circular queue?
• Both of these implementations won’t allow you to enqueue a new item if the queue is full. Can you think of some applications of a circular queue where this might be bad? How would we change the implementations to allow for over-writing?

Conclusion

I would encourage anyone reading this to look at other implementations around the web and compare them as well as think about different applications of the circular queue. I am still a student myself and still have a lot to learn. Nevertheless, I hope this might have been helpful for some of you learning about circular queues for the first time. Thanks for reading!