Stack Data Structure using Zig

Prerequisites

To get any meaningful value out of this post you should have an understanding of:

• Memory allocation
• Copying raw bytes using @memcpy
• Comptime generics
• Optionals

The Stack

The Story

There’s a box in front of you, about waist high. Behind you a wall with a mail slot. You hear the slot door open with a high pitch squeak as a plate slides through. As you reach for the plate you notice a number written on the surface. Ten. The plate seems to fit perfect in the box. You lay it down at the bottom and just as you release the plate you hear a familiar squeak as another plate slides through the mail slot. This time another number. Twenty. You grab the plate and place it on top of the previous in the box. Then another plate. Thirty. Fourty. Fifty.

[10, 20, 30, 40, 50]

You’ve formed a stack. An important structure in data organization. This methodology of adding and removing items from the box is called Last-In First-Out (LIFO). Here’s a link to my favorite cheatsheet. As you pile on top, in order to get to the items near the bottom you have to remove from the top. In our story if you wanted to reach plate 30 you’d need to remove 50 and 40 first. Putting things in the box is typically called push and removing is pop.

The Code

The values you’d want to store in a stack will vary depending on what type you’re working with. We’re going to start building our stack but we’re going to use Zig’s comptime metaprogramming to create a generic stack, one that can be used with any type. Let’s jump in.

pub fn Stack(comptime T: type) type {
  return struct {
    const Self = @This();

    allocator: std.mem.Allocator,
    buffer: []T,
    top: usize,

    pub fn init(allocator: std.mem.Allocator) Self {
      return Self{
        .allocator = allocator,
        .buffer = &[_]T{},
        .top = 0,
      };
    }

    pub fn deinit(self: *Self) void {
      self.allocator.free(self.buffer);
    }
  };
}

This is the skeleton of our stack. With this we can initialize a new stack of any type. In order to reference an instance of the anonymous struct we declare const Self = @This() within the struct. This will let us pass self: Self or self: *Self in methods where we need to reference an instance of our stack.

1. pub fn init(allocator: std.mem.Allocator) Self {}
   The init() function takes in an allocator. Our stack will manage it’s own memory.

2. return Self{ .allocator = allocator, .buffer= &[_]T{}, .top = 0 };
   We build our struct with the allocator, a buffer, and a pointer to the top of the stack. Our buffer holds a pointer to a slice of an unknown size of type T. Finally top will point to the top of the buffer, the next empty space in our buffer that we can push a value of type T.

3. pub fn deinit(self: *Self) void {}
   The last method in our skeleton is a way to deinit our stack. In practice we can defer this after declaring our stack to make sure we clean up after ourselves.

Okay, let’s talk stack specific logic:

pub fn Stack(comptime T: type) type {
  return struct {
    const Self = @This();

    allocator: std.mem.Allocator,
    buffer: []T,
    top: usize,

    pub fn init(allocator: std.mem.Allocator) Self {
      return Self{
        .allocator = allocator,
        .buffer = &[_]T{},
        .top = 0,
      };
    }

    pub fn deinit(self: *Self) void {
      self.allocator.free(self.buffer);
    }

+   pub fn resize(self: *Self, new_capacity: usize) !void {
+     const new_buffer = try self.allocator.alloc(T, new_capacity);
+     @memcpy(new_buffer[0..self.top], self.buffer[0..self.top]);
+     self.allocator.free(self.buffer);
+     self.buffer = new_buffer;
+   }
  };
}

Through our use of the stack we need to make sure our buffer has enough capacity to hold values of type T. We solve this in a similar way that Go resizes slices as it’s filled. Let’s go through this line by line.

pub fn resize(self: *Self, new_capacity: usize) !void {
  const new_buffer = try self.allocator.alloc(T, new_capacity);
  @memcpy(new_buffer[0..self.top], self.buffer[0..self.top]);
  self.allocator.free(self.buffer);
  self.buffer = new_buffer;
}

1. const new_buffer = try self.allocator.alloc(T, new_capacity);
   Here we allocate a new_buffer with capacity being set by the caller. We do this because the caller knows the size of the new buffer and can better determine what the new size should be.

2. @memcpy(new_buffer[0..self.top], self.buffer[0..self.top]);
   Then we copy the raw bytes from the current buffer self.buffer into new_buffer starting from index 0 until we reach self.top which should always point to the top of our stack.

3. self.allocator.free(self.buffer);
   Now that we have our bytes copied over we don’t need the old buffer so we free self.buffer to clean up.

4. self.buffer = new_buffer;
   Then replace self.buffer with the new_buffer.

We’ll need to call this sometimes when we push values onto the stack as you’ll soon see. Before we dive into how we push let’s discuss what role top plays. We initialize our stack with a top value of 0 because it’s empty, and the next buffer index used. Each time we push we increase top by 1 to point to the next empty index. When we pop we reduce by top by 1. Okay onto the code …

pub fn Stack(comptime T: type) type {
  return struct {
    const Self = @This();

    allocator: std.mem.Allocator,
    buffer: []T,
    top: usize,

    pub fn init(allocator: std.mem.Allocator) Self {
      return Self{
        .allocator = allocator,
        .buffer = &[_]T{},
        .top = 0,
      };
    }

    pub fn resize(self: *Self, new_capacity: usize) !void {
      const new_buffer = try self.allocator.alloc(T, new_capacity);
      @memcpy(new_buffer[0..self.top], self.buffer[0..self.top]);
      self.allocator.free(self.buffer);
      self.buffer = new_buffer;
    }

+   pub fn push(self: *Self, item: T) !void {
+     if (self.top >= self.buffer.len) {
+       try self.resize(if (self.buffer.len == 0) 1 else self.buffer.len * 2);
+     }
+     self.buffer[self.top] = item;
+     self.top += 1;
+   }
  };
}

1. if (self.top >= self.buffer.len) {} Each time we push a new value onto the stack we look at the top value. If this is equal to or larger than the length of our buffer, then we need more capacity to fit any new items. to do that we call …

   try self.resize(if (self.buffer.len == 0) 1 else self.buffer.len * 2);
   We evaluate our if statement which wants to multiply the existing buffer length by 2 as the new capacity, but we don’t want to do that if the current buffer is new since top will always be 0 for a new stack. The condition will result in the value 1 if top is 0, otherwise we multiply by 2.

2. self.buffer[self.top] = item;
   We put our value at the top of the buffer (at this point top should continue to point to the next empty space).

3. self.top += 1;
   Now we increment our “pointer” to the top of the stack so it continues to point to the next empty space.

pub fn Stack(comptime T: type) type {
  return struct {
    const Self = @This();

    allocator: std.mem.Allocator,
    buffer: []T,
    top: usize,

    pub fn init(allocator: std.mem.Allocator) Self {
      return Self{
        .allocator = allocator,
        .buffer = &[_]T{},
        .top = 0,
      };
    }

    pub fn resize(self: *Self, new_capacity: usize) !void {
      const new_buffer = try self.allocator.alloc(T, new_capacity);
      @memcpy(new_buffer[0..self.top], self.buffer[0..self.top]);
      self.allocator.free(self.buffer);
      self.buffer = new_buffer;
    }

    pub fn push(self: *Self, item: T) !void {
      if (self.top >= self.buffer.len) {
        try self.resize(if (self.buffer.len == 0) 1 else self.buffer.len * 2);
      }
      self.buffer[self.top] = item;
      self.top += 1;
    }

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

1. pub fn pop(self: *Self) ?T {}
   Here we return an optional since an empty buffer will have no items.

2. if (self.top == 0) return null;
   We assume that if top is 0 we’re pointing to the first index as available to put items into and there are no items to return.

3. self.top -= 1;
   Since top points to the next available index, we should reduce top by one to get the last value pushed before returning the buffer item.

4. return self.buffer[self.top];
   Finally, return the last pushed value to the caller.

At this point our stack is “good enough” to learn with. But we can add a couple more useful methods.

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

This peek method will let us look at the next item we’re about to pop before we do it.

pub fn is_empty(self: *Self) bool {
  return self.top == 0;
}

This is_empty method can be used to determine if our stack “is empty”. Be aware the buffer many not truly be empty since we use top as a pointer to move along our buffer.

Here’s an example of how we would use this stack.

const std = @import("std");

pub fn main() !void {
  const allocator = std.heap.page_allocator;
  var stack = Stack(i32).init(allocator);

  try stack.push(10);
  try stack.push(20);
  try stack.push(30);
  const last = stack.pop();

  if (last) |int| {
      std.debug.print("{d}\n", .{int});
  }
}

Our if condition here unwraps the result from pop. Because it could be empty we have to first check that it has a value. You can learn more about how to unwrap optionals here.

I hope this helps you view stacks from underneath the hood. One of the things I like most about Zig is it’s explicitness. It helps me understand how the machine is doing things and allows me to exert some control at a meaningful level. This is only an example of how Stacks work and we used Zig to accomplish that. This Stack has it’s own issues in that our buffer can contain junk data. However, as long as top is properly managed that should not cause issues when learning.

As an example, below is stack-like behavior using an ArrayList.

pub fn main() !void {
    const allocator = std.heap.page_allocator;
    var list = std.ArrayList(i32).init(allocator);

    try list.append(10);
    try list.append(20);
    try list.append(30);
    const last = list.pop();

    if (last) |int| {
      std.debug.print("{d}\n", .{int}); // 30
    }
}