01.08.2022 - Zig/Case Study: Implementing a Generic Stack

← All posts

Posted On 01.08.2022

Implementing a stack is one of my favorite tests when working with a new language because it will show us a lot about the language’s ergonomics.

We are going to make this stack a generic data structure. By Zig’s convention, it will be a function that takes a type comptime T for its elements and returns a type like this:

const std = @import("std");
 
pub fn Stack(comptime T: type) type {
    return struct {
    };
}

Our Stack is going to have the following methods:

• init(): Initialize the stack
• deinit(): Deinitialize the stack
• push(): Push a new item to the stack
• pop(): Remove and return the top item of the stack
• top(): Get the top item of the stack
• count(): Get the length of the items in the stack
• isEmpty(): Check if the stack is empty or not

We will use the built-in std.ArrayList to store data in our stack. It’s a contiguous and growable list data structure. ArrayList is also a generics data structure, so it’s suitable for our use case here:

const ArrayList = std.ArrayList;
 
...
return struct {
    stack: ArrayList(T),
 
    const Self = @This();
};
...

The const Self = @This() statement is another common pattern in Zig for self-reference to the current struct.

First, let’s implement init() and deinit() methods. The ArrayList.init method need to receive an Allocator as a parameter. When writing libraries in Zig, it’s best to let the user of the library decide which allocator they want to use. So, we will accept an Allocator parameter in our init() method:

pub fn init(allocator: Allocator) Self {
    return Self{ .stack = ArrayList(T).init(allocator) };
}
 
pub fn deinit(self: *Self) void {
    self.stack.deinit();
}

Before we implement the push() and pop() method, let’s talk about the order of data in our ArrayList. There are two ways to add an item to the list:

• Add a new item to the bottom of the list with the ArrayList.append() method. The top item of the stack will always be stack.items[stack.items.len - 1].
• Add a new item to the beginning (index 0) of the list with the ArrayList.insert() method. The top item of the stack will always be stack.items[0].

The ArrayList.insert() method (called with index 0) works by increasing the length of the list and moving all the items to the right before replacing the new data into the first item. The time complexity is always O(N). And we can insert the new item anywhere in the list.

The ArrayList.append() method always adds a new item at the end of the list and allocates a new memory as needed. So, time complexity will likely be O(1) for most of the time. If the Allocator fails to allocate new memory, this method will throw an error.

We are going to use ArrayList.append() for our push() method. The return type of this method is a union type !void, which means this function either returns nothing (void) or an error.

pub fn push(self: *Self, val: T) !void {
    try self.stack.append(val);
}

And the top item of our stack will be the last item of the list:

pub fn top(self: *Self) ?T {
    if (self.stack.items.len == 0) {
        return null;
    }
    return self.stack.items[self.stack.items.len - 1];
}

To implement the pop() method, we are going to use ArrayList.popOrNull(), which will either remove and return the last item in the list or just return a null value if the list is empty:

pub fn pop(self: *Self) ?T {
    return self.stack.popOrNull();
}

There is not much to say about count() and isEmpty() methods, so I will skip ahead and show the full implementation of our stack, as well as the tests:

const std = @import("std");
const ArrayList = std.ArrayList;
const Allocator = std.mem.Allocator;
 
pub fn Stack(comptime T: type) type {
    return struct {
        stack: ArrayList(T),
 
        const Self = @This();
 
        pub fn init(allocator: Allocator) Self {
            return Self{ .stack = ArrayList(T).init(allocator) };
        }
 
        pub fn deinit(self: *Self) void {
            self.stack.deinit();
        }
 
        pub fn push(self: *Self, val: T) !void {
            try self.stack.append(val);
        }
 
        pub fn pop(self: *Self) ?T {
            return self.stack.popOrNull();
        }
 
        pub fn top(self: *Self) ?T {
            if (self.stack.items.len == 0) {
                return null;
            }
            return self.stack.items[self.stack.items.len - 1];
        }
 
        pub fn count(self: *Self) usize {
            return self.stack.items.len;
        }
 
        pub fn isEmpty(self: *Self) bool {
            return self.count() == 0;
        }
    };
}

Some tests:

test {
    const expect = std.testing.expect;
 
    var gpa = std.heap.GeneralPurposeAllocator(.{}){};
    defer std.debug.assert(!gpa.deinit());
 
    const IntStack = Stack(i32);
 
    var stack = IntStack.init(gpa.allocator());
    defer stack.deinit();
 
    try stack.push(1);
    try stack.push(2);
    try stack.push(3);
 
    try expect(stack.isEmpty() == false);
 
    try expect(stack.top().? == 3);
    try expect(stack.pop().? == 3);
    try expect(stack.top().? == 2);
    try expect(stack.pop().? == 2);
    try expect(stack.top().? == 1);
    try expect(stack.pop().? == 1);
 
    try expect(stack.isEmpty() == true);
}

---