Data Structures: Your Quick Intro to Circular Buffers
Have you ever opened your computer and started typing your password just to see a major lag in what you’re typing? This lag happens when the computer processor wakes up and realizes it needs to start grabbing data from the mini processor in the keyboard. But how is this information stored if there’s just a tiny bit of space in the keyboard’s memory?
This is where the circular buffer comes in.
The circular buffer is a certain type of queue. Now if you’re not familiar with a queue, you might know it as a line. (Like when you’re waiting in line to use the restroom.) This queue is a first in, first out (FIFO) structure. That means the first person to enter a line is the first person to exit. So what is different about a circular queue?
A circular buffer stores data in a fixed-size array. So once the size is set and the buffer is full, the oldest item in the buffer will be pushed out if more data is added. By storing two pointers to the front and back of the structure, there is no need to dynamically manipulate the array.
However, if the buffer is full and you need to add something new, simply set the list item pointed to by the back pointer to the new item and increment the back pointer by one. The front will now point to the most recently added item.
This technique of memory allocation has benefits when you’re working with a lot of data in real time. As more data is added to the structure, the old data will be removed so no data will ever need to be shifted. As stated before, the pointers just shift positions.
Now to get back to your keyboard and password input. All of your keystrokes are held in a circular buffer. So if you typed fast enough, you would potentially lose some of the input received from the keystrokes.
The Circular Buffer Restaurant
To help imagine the circular buffer, let’s build an automated restaurant. This restaurant has a single pick-up window (the back of the buffer) where one customer at a time can pick up their meal (the data). Behind the window is a rotating, circular table that holds 8 meals (the buffer). There is also a light that points to the front of the table (or the front of the buffer). Every time a meal is taken from the window, the table rotates clockwise one spot.
When the chef has finished cooking a meal, he places it one spot in front of the place that is lit up. The light then shines on the newly placed dish. If the buffer is full and a meal is ready to come off the stove, the meal at the window will be dumped into the trash. The table will rotate, and the new meal will be placed in the empty spot.
Use Cases
An instructor once told me about an augmented reality tech firm that used a circular buffer to hold frames of the movements input by the user. They recorded the motion of user’s hand and body movements and streamed it to a display in real time. If a user input a lot of movements in a short period of time, the movements would be stored.
When you rewind a few minutes of a streaming movie or TV show, those previous frames have been stored in a circular buffer so that they can be accessed quickly. If you rewind more frames than are stored in the buffer, it will take more time to reload the frames you are searching for.
In conclusion, if you need to quickly access streaming data that has already been observed or used, a circular buffer might be a good solution!
Resources
Here is a link to my implementation of a circular buffer.
