Python circular queues

The circular queue is a data structure that I have used a lot to solve communication problems. It is as simple as useful.

From wikipedia:

“A circular buffer, circular queue, cyclic buffer or ring buffer is a data structure that uses a single, fixed-size buffer as if it were connected end-to-end. This structure lends itself easily to buffering data streams.

The useful property of a circular buffer is that it does not need to have its elements shuffled around when one is consumed. (If a non-circular buffer were used then it would be necessary to shift all elements when one is consumed.) In other words, the circular buffer is well-suited as a FIFO buffer while a standard, non-circular buffer is well suited as a LIFO buffer.

Circular buffering makes a good implementation strategy for a queue that has fixed maximum size. Should a maximum size be adopted for a queue, then a circular buffer is a completely ideal implementation; all queue operations are constant time. However, expanding a circular buffer requires shifting memory, which is comparatively costly. For arbitrarily expanding queues, a linked list approach may be preferred instead.”

Some years ago I wrote another post about the circular queues, in this post “A simple implementation of a circular queue in C language” you can find a little bit of theory and definitions, and also some the C implementation.

Circular queues in Python

since I have to synchronize the access between threads, the first thing I do is the implementation of the synchronization logic. I explained this decorator in the post Python decorators in the real world. All the methods that can be accessed from outside the class will be decorated.

Let’s start with the circular queue implementation. It will be a class with the following properties:
queue: a list of items (initialized to none)
head: the index of element to be popped from the queue
tail: the index of the element where the next push will be done

q_size: the maximum number of elements in the queue

The first method I add is a method that computes the number of valid items in the queue.
If the index of the tail element is greater or equal to the index of the head of the queue, the numebr of valid items is the difference between. Otherwise I have to apply a wrap around and the number of valid items will be comupted as the max number of items in the queue minus the index of the head element plus the index of the tail element.

Let’s enqueue an element, an element can be enqueued if the number of valid elements is less than the max number of elements.

And the dequeue method….

Last, to observe the content of the queue a simple print function

to test our queue we need a couple of threads, a producer thread and a consumer thread which will use the queue

You can find the full source code on my github at cqueue.py

Gg1

Related Posts

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.