Implementing a Circular Queue in C

---

Implementing a Circular Queue in C // Queues are a fundamental data structure that every programmer needs in their toolbox. A year ago, I showed you how to implement a queue using a linked list. In this video, I show you how to implement a circular queue using an array, in C.

Related Videos:



***

Welcome! I post videos that help you learn to program and become a more confident software developer. I cover beginner-to-advanced systems topics ranging from network programming, threads, processes, operating systems, embedded systems and others. My goal is to help you get under-the-hood and better understand how computers work and how you can use them to become stronger students and more capable professional developers.

About me: I'm a computer scientist, electrical engineer, researcher, and teacher. I specialize in embedded systems, mobile computing, sensor networks, and the Internet of Things. I teach systems and networking courses at Clemson University, where I also lead the PERSIST research lab.

More about me and what I do:

To Support the Channel:
+ like, subscribe, spread the word

[michaelkotthaus]

Thank you, Jacob. This is again a very helpful video for understanding the data structure which I usually call ring buffer (actually Ringpuffer).
I like to suggest to make the functions enqueue and dequeue thread-safe. There are a lot of embedded applications where one thread writes to the queue and another reads from it, for example in conjunction with a serial interface.
To achieve this thread-safety I would first get rid of the num_entries which is changed by both functions. The number of entries can be calculated from head and tail. Also, one element in the queue must be reserved to distinguish between empty and full. So, the queue is empty if head == tail. In contrast, the queue is full if (head - tail + size) % size == 1. But often no separate functions are needed for this: if enqueuing fails, the queue is full (or not initialized). If dequeuing fails, the queue is empty (or not initialized).

[austingrossman]

Thanks for the quality product. Circular buffers are one of my favs. I've always had the head as the element changing for adding data and tail for removing data; now you have me second-guessing lots of code in my past.

Also mentioned in another comment, making this more thread safe is a must. Usually you'll have one thread using enqueue and another using dequeue exclusively. The only problem area is the use of num_entries.

[kissingfrogs]

Thanks Jacob, I learnt much and have a working queue.

[valeryivanov]

Where you have been a few days ago, Jacob?
Today I was implemented this Circular Queue in interview :)

Thank you!

[diceandbricks]

Very nice tutorial. Alternative to tracking num_entries, you can calculate it from head and tail.

[TheCocoaDaddy]

Great video! Using the modulus operator can be quite handy! Thanks for posting!

[strengthstamleatherbeltl]

You're a great teacher. I sort of understood before, but now I really do. Thanks!

[sunnybeta_]

Holy shit I found a gem of a channel for C 😍 subscribed and gettin some popcorn :D

[sumitnegiu]

Thanks jacobs, Video was very helpful .

[tbprodutions]

I tried doing this before but without num_entries and it almost worked, but I kept having problems with keeping track of data.

[melvinthomas]

I was thinking about how to circular buffer for a loging mechanism i needed

[benjaminshinar]

always great to see some basic C code!

can you do something about shared memory between process?

[matmya]

8:00 also good technique is to not use modulo operator, because of the division operation cost, instead use circular queue size with power of 2 then the index pointer will just simply overflow.

[integral]

hey, what file icon theme do you use, nice vids btw, you taught me everything I didn't have to learn myself about C.

[pranavbharadwaj]

Hi Jacob !! I have a need to implement a circular buffer for an UART implementation, where I can write any number of bytes to the buffer, and read any number of bytes from it. How do I go about implementing this ? For example, a static array of size 128 bytes is initialized. As input, I would provide a pointer to the data being stored in the buffer and the size of it in number of bytes. If the number of bytes in input exceeds the array size, we store as much as we can fit into the array and throw away the rest.

[EdwinFairchild]

wouldnt a circular queue allow you to enqueue even if its full and thus a new value will over write the oldest one (tail) thus a circular queue, or would that be a circular buffer?

[fuzeti_ale]

Can i free the entire queue? I dont know how i should do it.

[dryaserdryaser]

Do you have any good C courses to recommend? I'm in my first semester and I literally have no idea what is going on in class.

[ejsseig]

Great content. Extremely helpful, really.

[bollojuaravind]

Brother @Jacob Sorber I have seen this queues with array .. but it is 1D array.... Like we are dequeuing only single element right... What if we need an array in place of that single element... Can we able to do 2D array queues? So every time when we dequeue a 1D array of size N can be dequeued from it... Can you please suggest