In my second year of university, I took a class that involved a series of AVR assembly language programming labs. One of them required an implementation of a queue data structure. It was meant to be a simple lab, but an early design decision made it needlessly complicated. This additional complexity single-handedly turned debugging into a nightmare.

My Epic Fail Queue Implementation

My implementation required that all elements be butted up to the front of the buffer. One pointer points to the back.

+---+---+---+---+---+---+
| A | B | C |   |   |   |
+---+---+---+---+---+---+
          ^
          Back

Enqueueing items would add to the back of the queue, and the Back pointer is updated in the process:

+---+---+---+---+---+---+
| A | B | C | D |   |   |
+---+---+---+---+---+---+
              ^
              Back

Dequeuing would require us to take from the front and shift the remaining elements forward to fill in the space:

+---+---+---+---+---+---+
| B | C | D |   |   |   |
+---+---+---+---+---+---+
          ^
          Back

Hopefully it should be obvious that this makes dequeuing so expensive to accomplish (O(n)) since you’d have to read and write across all the remaining elements in order to do the shifting.

This mistake of choosing the wrong queue implementation bloated the code up by requiring an unnecessarily complex dequeue function to be implemented, and since the function didn’t work the first time around, it took at a nightmarish night of debugging.

The program was failing in such weird ways, and there were so many other possible points of failure, with so many subsystems concurrently running and accessing data all at once. Remember, this is assembly language we’re talking about! If the dequeue function were simpler, I could’ve quickly “proved” that it works as expected, thus allowing me to focus on other places.

In the end, the dequeue function was the problem.

When I proudly presented the final working program to the lab demonstrator, while he was impressed that I got such a thing to work, he was shocked that I even attempted to implement such a thing in the first place. “You realize you could’ve implemented this with a circular buffer, right?”

The Circular Buffer

In a circular buffer, your queue contents are continguously contained somewhere within the queue, not necessarily at the front or back. Two pointers point to the beginning and end.

          Front
          v
+---+---+---+---+---+---+
|   |   | A | B | C |   |
+---+---+---+---+---+---+
                  ^
               Back

Dequeuing would simply grab whatever’s at the front and update the pointer:

              Front
              v
+---+---+---+---+---+---+
|   |   |   | B | C |   |
+---+---+---+---+---+---+
                  ^
               Back

And enqueing would simply add to the back and update the pointer:

              Front
              v
+---+---+---+---+---+---+
|   |   |   | B | C | D |
+---+---+---+---+---+---+
                      ^
                   Back

If the end of the buffer is reached, we simply wrap to the end, using modular arithmetic to start reading from the beginning again:

              Front
              v
+---+---+---+---+---+---+
| E |   |   | B | C | D |
+---+---+---+---+---+---+
  ^
  Back

Simple and fast!

The Takeaway

The really obvious takeaway here is to make sure you evaluate your data structures and implementations properly, otherwise you end up giving yourself so much pain later on.

But for me personally, I think at the time, I was a bit too dangerously relaxed about the whole topic of data structures. At that point, I never experienced just how much worse poor design decisions can make everything.

To me, this was a painful yet valuable lesson in ensuring the suitability of a design, and it highlights the importance of mastering and internalizing understanding of data structures and algorithms.