You have used a queue today—probably dozens of times. Waiting at the supermarket checkout. Messages loading in order on your phone. Background tasks processing on your server. The queue data structure is everywhere because it solves a fundamental problem: making sure things happen in the right order, without overwhelming your system.
Think of waiting at a supermarket checkout. You join the back of the line and wait for your turn, whilst the cashier deals with the person at the front.
In computing, a queue works exactly the same way—it is a line of data waiting to be processed. Whether you are processing webhook events in the order they arrive, handling print jobs sent to a shared printer, or managing background tasks in a web application, the queue ensures everything happens in the right sequence. This makes it essential for handling concurrent tasks, message passing between threads, and building systems like message brokers and event loops.
In this article, we will implement a Queue from scratch in Zig to understand the fundamental mechanics and performance trade-offs. While the code is in Zig, the explanation and simplicity of the logic will help you implement something similar in Rust, C, or whichever language you prefer.
Fundamental and Core Operations
A Queue follows a First-In, First-Out (FIFO) principle. This is why you'll often hear it called a FIFO Queue or just FIFO. The structure is like a pipe: the first item to enter one end is the first to exit the other. You can't reach into the middle and pull an item out. This sequential processing is exactly how many systems, from HTTP servers to event streaming platforms, handle requests.
In technical terms, the entry point is called the back (or tail), and adding an item is called an enqueue operation. The exit point is the front (or head), and removing an item is a dequeue operation.
For a queue to be reliable in high-performance or concurrent systems, enqueue and dequeue must be fast. Specifically, they need to complete in constant time—often written as O(1) time complexity. This means the operation takes the same amount of time regardless of whether the queue holds two items or two million. If an operation slows down as the queue grows, it creates a bottleneck. This performance guarantee is the central engineering challenge we must solve.
Building the Queue Struct in Zig
Even though most standard libraries provide a queue implementation, building one yourself is a fantastic way to understand its inner workings. We will start with a simple implementation, then solve its biggest problem using a technique called a circular buffer.
Let's begin with the basics. In Zig, we can create a generic function that returns a custom type. Think of it like a template in C++ or generics in other languages. The comptime keyword means this happens at compile time.
Before we dive into the code, here's a quick note about Zig's error handling: the try keyword propagates errors up the call stack, similar to the ? operator in Rust or throwing exceptions in other languages. When you see try queue.enqueue(10), it means "attempt this operation, and if it fails, return the error to the caller."
const std = @import("std");
// Helper function for logging
fn log(value: i32) void {
std.debug.print("{d}\n", .{value});
}
// A generic function to create a Queue type with a specific capacity.
fn Queue(comptime capacity: usize) type {
return struct {
// The array that will store our queue's elements.
data: [capacity]i32 = [_]i32{0} ** capacity,
// 'front' is the index of the next element to be dequeued.
front: usize = 0,
// 'back' is the index where the next element will be enqueued.
back: usize = 0,
// 'count' tracks the current number of elements in the queue.
count: usize = 0,
// A constant to refer to the struct itself. A common Zig pattern.
const Self = @This();
// Adds an item to the back of the queue.
pub fn enqueue(self: *Self, value: i32) !void {
if (self.count >= capacity) {
return error.QueueFull;
}
self.data[self.back] = value;
self.back += 1;
self.count += 1;
}
// Removes an item from the front of the queue.
pub fn dequeue(self: *Self) !i32 {
if (self.count == 0) {
return error.QueueEmpty;
}
const value = self.data[self.front];
self.front += 1;
self.count -= 1;
return value;
}
};
}
Let's break down that array initialisation syntax, as it is quite specific to Zig. When you write [_]i32{0} ** capacity, you're telling the compiler to create an array filled with zeros. The [_] syntax means "infer the size from what follows." The {0} is your initialiser value, and the ** operator repeats that value to fill the entire array. So if capacity is 4, this expands to an array with four zeros: [4]i32{0, 0, 0, 0}. It is a compact way to initialise arrays without manually writing out each element.
A few other Zig-specific details worth noting: The !void and !i32 return types mean these functions can return either a value or an error. The *Self parameter means we're passing a pointer to the struct, allowing us to modify it. The @This() built-in function returns the type of the current struct. It is Zig's way of avoiding repetition when you need to refer to your own type.
Here's how you would use it:
var queue = Queue(4){};
try queue.enqueue(10);
try queue.enqueue(20);
try queue.enqueue(30);
// Dequeue and print data
log(try queue.dequeue());
log(try queue.dequeue());
Which prints:
10
20
This seems to work well, but there's a critical flaw lurking beneath the surface.
The Problem: Running Out of Space When There Is Room
Imagine you create a queue with capacity for four items. You add four items, then remove two. Your queue now has two items in it, with plenty of space. But here is the trap: self.back is now at index 4 (the end of the array), while self.front is at index 2. If you try to add another item, the code will try to write to data[4], which is out of bounds!
Our queue with a capacity of 4:
┌───┬───┬───┬───┐
│10 │20 │30 │40 │ data
└───┴───┴───┴───┘
0 1 2 3 (indices)
After two dequeues:
┌───┬───┬───┬───┐
│ │ │30 │40 │ (Logically empty)
└───┴───┴───┴───┘
↑ ↑
front=2 back=4
The problem: `back` is at the end. We have two empty slots at the start, but our simple logic cannot see them. The queue is effectively broken.
We could fix this by shifting all elements back to the start of the array after each dequeue, similar to how people in a physical checkout queue shuffle forward. But that is expensive. Moving elements takes more time as the queue grows, which breaks our promise of constant-time operations. We need something better.
The Solution: Circular Buffers (Ring Buffers)
The elegant solution is to treat the array as circular. Instead of thinking of it as a line with a start and end, imagine it as a ring. When you reach the last position, you wrap around to the beginning. This is called a circular buffer or ring buffer.
Here's a text-based visualisation of how this works. Imagine a queue with capacity for 4 items. To make the logic work (as we will explain in a moment), we actually use 5 slots in memory:
Initial state (empty queue):
┌───┬───┬───┬───┬───┐
│ │ │ │ │ │
└───┴───┴───┴───┴───┘
↑
front = 0, back = 0
After enqueue(10), enqueue(20), enqueue(30):
┌───┬───┬───┬───┬───┐
│10 │20 │30 │ │ │
└───┴───┴───┴───┴───┘
↑ ↑
front = 0 back = 3
After dequeue() twice:
┌───┬───┬───┬───┬───┐
│ │ │30 │ │ │
└───┴───┴───┴───┴───┘
↑ ↑
front = 2 back = 3
Now enqueue(40), enqueue(50) — watch the wrap-around:
1. We enqueue(40). `back` moves from 3 to 4.
2. We enqueue(50). `back` tries to move from 4 to 5. Using our modulo formula `(4 + 1) % 5`, it wraps around to 0. The value `50` is placed at index 0. `back` now points to the *next* empty slot, which is 1.
┌───┬───┬───┬───┬───┐
│50 │ │30 │40 │ │
└───┴───┴───┴───┴───┘
↑ ↑
back = 1 front = 2
The queue is now storing `30`, `40`, and `50`. The `front` pointer is at index 2 (ready to dequeue `30`), and the `back` pointer is at index 1 (ready for the next enqueue). The wrap-around worked perfectly!
The key to making this work is understanding how we calculate the wrap-around. When we want to move to the next position, we use this formula:
next_position = (current_position + 1) % array_size
The % symbol is the modulo operator. It gives you the remainder after division. Here's how it creates the wrap-around effect:
-
(0 + 1) % 5 = 1— moving from index 0 to 1 -
(1 + 1) % 5 = 2— moving from index 1 to 2 -
(2 + 1) % 5 = 3— moving from index 2 to 3 -
(3 + 1) % 5 = 4— moving from index 3 to 4 -
(4 + 1) % 5 = 0— here's the magic! Moving from index 4 wraps back to 0
When you divide 5 by 5, you get 1 with a remainder of 0. The modulo operator gives us that remainder. This is why it works so perfectly for circular buffers—any number divided by the array size will always give you a remainder between 0 and (array_size - 1), which are exactly the valid indices of our array.
The Extra Slot Trick
There is one clever trick we need: we allocate capacity + 1 slots instead of just capacity. This extra slot helps us distinguish between "completely full" and "completely empty."
Here is why this matters. Without the extra slot, imagine a 3-item queue with 3 slots:
Empty queue: Full queue:
┌───┬───┬───┐ ┌───┬───┬───┐
│ │ │ │ │10 │20 │30 │
└───┴───┴───┘ └───┴───┴───┘
↑ ↑
front = 0, back = 0 front = 0, back = 0 (after wrapping)
Both states look identical! When front equals back, we cannot tell if we have zero items or three items. The queue is ambiguous.
With the extra slot, we get this behaviour:
Empty queue (4 slots for 3 items):
┌───┬───┬───┬───┐
│ │ │ │ │
└───┴───┴───┴───┘
↑
front = 0, back = 0
Full queue (3 items stored):
┌───┬───┬───┬───┐
│10 │20 │30 │ │ ← One slot always remains empty
└───┴───┴───┴───┘
↑ ↑
front = 0 back = 3
Now it is clear: the queue is full when back is one position
behind front (with wrapping). The queue is empty when they are equal.
The queue is full when the next position after back would equal front. This means we always keep one slot empty as a sentinel, making the full/empty detection unambiguous.
A sentinel is a special value used to indicate a particular state, such as the end of a data structure or a specific condition being met. In this case, the empty slot acts as a sentinel to differentiate between full and empty states of the queue.
Here is the complete implementation:
fn Queue(comptime capacity: usize) type {
return struct {
// We allocate one extra slot to distinguish full from empty
data: [capacity + 1]i32 = [_]i32{0} ** (capacity + 1),
front: usize = 0,
back: usize = 0,
const Self = @This();
pub fn enqueue(self: *Self, value: i32) !void {
// Calculate where 'back' would be after adding this item
// The modulo ensures we wrap around to 0 if we exceed capacity
const next_back = (self.back + 1) % (capacity + 1);
// If that would make back equal front, we are full
if (next_back == self.front) {
return error.QueueFull;
}
self.data[self.back] = value;
// Move back to its new position (wrapping around if needed)
self.back = next_back;
}
pub fn dequeue(self: *Self) !i32 {
// If front equals back, the queue is empty
if (self.front == self.back) {
return error.QueueEmpty;
}
const value = self.data[self.front];
// Move front forward, wrapping around if we reach the end
self.front = (self.front + 1) % (capacity + 1);
return value;
}
pub fn isEmpty(self: *const Self) bool {
return self.front == self.back;
}
pub fn isFull(self: *const Self) bool {
return (self.back + 1) % (capacity + 1) == self.front;
}
};
}
Notice we no longer need the count field. We can determine whether the queue is empty or full just by comparing front and back. Both enqueue and dequeue remain constant-time operations. No matter if the queue holds two items or two thousand, the operations take the same amount of time because we are just updating indices, not moving data around.
Let's test it with a more thorough example to see the circular behaviour in action:
var queue = Queue(3){}; // Capacity of 3 items
try queue.enqueue(10); // back moves from 0 to 1
try queue.enqueue(20); // back moves from 1 to 2
try queue.enqueue(30); // back moves from 2 to 3
log(try queue.dequeue()); // 10 - front moves from 0 to 1
log(try queue.dequeue()); // 20 - front moves from 1 to 2
// Now we can add more items, reusing the space at the front
try queue.enqueue(40); // back moves from 3 to 0 (wraps around!)
try queue.enqueue(50); // back moves from 0 to 1
log(try queue.dequeue()); // 30 - front moves from 2 to 3
log(try queue.dequeue()); // 40 - front moves from 3 to 0 (wraps around!)
log(try queue.dequeue()); // 50 - front moves from 0 to 1
Which prints:
10
20
30
40
50
This circular buffer technique is used in many applications in systems programming—from audio processing buffers to network packet queues—because it is simple, fast, and memory-efficient.
Why Arrays Over Linked List?
You can implement a Queue using a Linked List as well. You might wonder: why not use a Linked List? They can grow dynamically without a fixed capacity, which sounds appealing on the surface.
The answer comes down to how modern computers actually work.
Arrays store data in one contiguous block of memory. This means your CPU can load chunks of it into its cache all at once. Think of it like reading a book—it is much faster to read the next page when the book is already open in front of you, rather than walking to a library shelf to fetch every single page individually.
Linked List scatter data across memory, forcing the CPU to jump around to find the next item. Those jumps are expensive. In real-world systems, scattered memory access can be 10 to 100 times slower than sequential array access. When you are handling thousands of queue operations per second, that performance difference compounds quickly.
There is also the allocation cost. Every enqueue operation with a Linked List requires asking the system for memory—a "syscall" that involves context switching and bookkeeping. With an array-based Queue, you just write to a pre-allocated slot. It is the difference between renting a new storage unit every time you need to store a box versus having a warehouse ready and waiting.
For most use cases, especially in performance-critical systems, the array-based circular buffer strikes the best balance. You get predictable memory usage, excellent cache performance, no allocation overhead, and guaranteed constant-time operations.
Wrap Up
The queue is a simple yet powerful data structure that operates on a FIFO principle, making it perfect for processing tasks in order. We have built a complete, working implementation using a circular buffer—a technique that solves the "running out of space" problem while maintaining constant-time performance.
I encourage you to try implementing this queue in your favourite programming language. The circular buffer pattern translates well to any language with arrays and basic arithmetic. Whether you are working in Rust, C, Go, or even higher-level languages like Python or JavaScript, the concepts remain the same.
In the next article, we will tackle concurrent queues—how to make this data structure safe when one thread produces items while another consumes them. This single-producer, single-consumer pattern is crucial for building high-performance systems. Want to be notified when it is published? Subscribe at pmbanugo.me and feel free to share this with colleagues who would benefit from understanding the fundamentals.
Top comments (0)