Up tonight, I’m going to write a queue implementation using a vector in Clojure and a fixed-size array in Go. The reason for the latter is that the Data Structures course on Coursera shows an interesting way of making a queue work when the backing data structure is of fixed size.
Essentially, what I will do is implement a circular buffer. As items are popped off the front of the queue to be worked on, I’ll have two pointers that will wrap around to the beginning of the array as needed.
Before I get ahead of myself, though, I’m going to do the easy thing first and write a simple implementation in Clojure.
Queue in Clojure with a vector
As I said in the original post, Clojure has a
list data structure that is optimized for pushing items to the front of it and a
vector data structure whose optimization is for pushing to the back of it. The latter one sounds perfect for a queue implementation.
As per usual, I’m going to store the state in an
1 2 3 4 5 6 7 8 9 10 11 12
Here’s the usage of it.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
The implementation is straightforward, eased by the tools built into Clojure.
conj pushes to the back of a
vector. Using an
atom and its interface (
reset!) allows me to easily pop the item off the queue and return it. Making new things in Clojure using the existing things is as simple and enjoyable as advertised.
Queue in Go using a fixed-size array
Now, I’m going to up the challenge a bit. Go is one of few languages intended to replace C. Well, at least, that’s how I look at it. It doesn’t have the niceties of other languages similar in age. There are no generics, for example, so there is no generalized data structure interface like there is in Clojure.
There is, however, a nice(-ish) implementation of an array. I’m going to try using that to create a queue.
Go seems to me to be a verbose language, not due to being overly ceremonious like Java, but because it seems as if it’s a DIY language. It gives you some basic stuff, but the rest is up to you. Some like that. I don’t know if I do.
Since I have nearly 0 experience in it, my implementation is likely to be circumlocutory (LOL, thesaurus). I’m going to split it into two sections:
dequeue. These are implemented as methods on a
struct, so that I can encapsulate the computation of the
writeIdx. It’s kind of OOP in its approach.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24
The interesting part here is keeping track of the
writeIdx value. Since I’m using a fixed size array, I need to detect when I’ve moved the
writeIdx past the end of the array and reset it to the head. I also need to detect when I’ve ran out of space in the array, so that I don’t overwrite items in the queue. Here’s how that would look.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
queueables slice is there just so that I can easily add items to the queue. One o the idioms in Go is to return an error type from a call. I am using that to print out the error when I’ve run out of space in my queue.
fmt.Println outputs things nicely,
0 3 [21 11 1 3] Queue is full. Number 40 is not added to the queue, since there is no space left.
on to dequeue
The above test will only ever enqueue and it’ll run out of space quickly. For a queue to be useful, it needs to have items removed, as well. Removing items from a queue needs to update the
readIdx pointer value. Having this value be equal to
writeIdx would mean that the queue is empty.
1 2 3 4 5 6 7 8 9 10
The item is fetched using the existing
readIdx value, then calculations are made to ensure that the
readIdx also wraps around the end of the array (slice, whatever). This makes implementing
1 2 3 4 5 6 7 8 9 10 11
The full test output then looks like this:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26
Challenges and conclusion
It’s fairly simple and easy to implement queues and stacks using dynamically-sized backends. Well, at least, it’s simple and easy to do the basics. The backend scales up and down as needed and the programmer is left with focusing on the behaviour of each data structure. The tradeoff is that queues and stacks that use dynamically-sized backends (like a linked list) are essentially unbounded. In the worst case scenario, this could cause OoM (Out of Memory) errors on the machine running the implementation.
Writing a basic bounded queue implementation using a circular array has been more challenging. It made me appreciate not just the complexities around keeping track of read and write indexes, but also API design. As the client programmer, I wouldn’t want to keep track of that. All I want is to push items onto a queue, remove them from it and check its state. This has been an illuminating exercise.