# The Basic Difference ### Queues and Stacks Queues and stacks are two simple ways to organize a collection of items. They are not complicated data structures. Their power comes from the rules they enforce. A stack gives you the last item first. A queue gives you the first item first. These rules appear everywhere in programming: parsers, schedulers, interpreters, graph algorithms, job systems, undo history, message processing, and event loops. ## The Basic Difference A stack is last-in, first-out. ```text push 10 push 20 push 30 pop -> 30 pop -> 20 pop -> 10 ``` The last item added is the first item removed. A queue is first-in, first-out. ```text enqueue 10 enqueue 20 enqueue 30 dequeue -> 10 dequeue -> 20 dequeue -> 30 ``` The first item added is the first item removed. | Structure | Add operation | Remove operation | Rule | |---|---|---|---| | Stack | push | pop | Last in, first out | | Queue | enqueue | dequeue | First in, first out | ## Stacks A stack behaves like a pile of plates. You add to the top. You remove from the top. ```text top [30] [20] [10] bottom ``` The basic operations are: ```text push: add an item pop: remove the most recent item peek: look at the most recent item without removing it ``` ## Building a Stack with ArrayList In Zig, the easiest beginner stack is an `ArrayList`. Appending to the end is `push`. Removing from the end is `pop`. ```zig const std = @import("std"); pub fn main() !void { var gpa = std.heap.GeneralPurposeAllocator(.{}){}; defer _ = gpa.deinit(); const allocator = gpa.allocator(); var stack = std.ArrayList(i32).init(allocator); defer stack.deinit(); try stack.append(10); try stack.append(20); try stack.append(30); const a = stack.pop(); const b = stack.pop(); std.debug.print("{} {}\n", .{ a, b }); } ``` Output: ```text 30 20 ``` The last value appended was `30`, so it comes out first. ## Stack Push This is the push operation: ```zig try stack.append(10); ``` It may allocate memory, so it uses `try`. Appending to an `ArrayList` is usually fast. Sometimes the list must grow its internal buffer, so the operation can allocate. ## Stack Pop This is the pop operation: ```zig const value = stack.pop(); ``` In many Zig versions, `pop()` removes and returns the last item. The exact return type can vary across standard library versions, so check your installed Zig docs when writing production code. A safe beginner pattern is to check the length before popping: ```zig if (stack.items.len > 0) { const value = stack.pop(); std.debug.print("{}\n", .{value}); } ``` This avoids popping from an empty stack. ## Stack Peek To look at the top item without removing it, read the last element: ```zig if (stack.items.len > 0) { const top = stack.items[stack.items.len - 1]; std.debug.print("top = {}\n", .{top}); } ``` The index is: ```zig stack.items.len - 1 ``` because indexes start at zero. For this stack: ```text [10][20][30] ``` the length is `3`, and the last index is `2`. ```text index: 0 1 2 value: 10 20 30 ``` ## A Small Stack Wrapper You can wrap `ArrayList` in your own stack type. ```zig const std = @import("std"); const Stack = struct { items: std.ArrayList(i32), pub fn init(allocator: std.mem.Allocator) Stack { return Stack{ .items = std.ArrayList(i32).init(allocator), }; } pub fn deinit(self: *Stack) void { self.items.deinit(); } pub fn push(self: *Stack, value: i32) !void { try self.items.append(value); } pub fn pop(self: *Stack) ?i32 { if (self.items.items.len == 0) return null; return self.items.pop(); } pub fn peek(self: *Stack) ?i32 { if (self.items.items.len == 0) return null; return self.items.items[self.items.items.len - 1]; } }; ``` Using it: ```zig pub fn main() !void { var gpa = std.heap.GeneralPurposeAllocator(.{}){}; defer _ = gpa.deinit(); var stack = Stack.init(gpa.allocator()); defer stack.deinit(); try stack.push(10); try stack.push(20); if (stack.pop()) |value| { std.debug.print("{}\n", .{value}); } } ``` Output: ```text 20 ``` This wrapper gives your code clearer names. Instead of exposing every `ArrayList` operation, you expose only stack operations. ## Why Stacks Matter Stacks appear naturally when a program must remember nested work. Examples: ```text function calls expression parsing undo history depth-first search matching parentheses temporary compiler state ``` When a function calls another function, the program uses a call stack. When a parser enters nested parentheses, it often uses a stack. When an editor implements undo, the most recent change is undone first. That is stack behavior. ## Queues A queue behaves like a line of people. The first person in line is served first. ```text front back [10] -> [20] -> [30] ``` The basic operations are: ```text enqueue: add an item to the back dequeue: remove an item from the front peek: look at the front item without removing it ``` ## A Simple Queue with ArrayList You can build a beginner queue using `ArrayList`. ```zig const std = @import("std"); pub fn main() !void { var gpa = std.heap.GeneralPurposeAllocator(.{}){}; defer _ = gpa.deinit(); const allocator = gpa.allocator(); var queue = std.ArrayList(i32).init(allocator); defer queue.deinit(); try queue.append(10); try queue.append(20); try queue.append(30); const first = queue.orderedRemove(0); const second = queue.orderedRemove(0); std.debug.print("{} {}\n", .{ first, second }); } ``` Output: ```text 10 20 ``` This works, but it has a cost. Every time you remove index `0`, the remaining items shift left. ```text Before: [10][20][30][40] Remove 10: [20][30][40] ``` For small queues, this is fine. For large queues, it can become expensive. ## Better Queue Design: Head Index A better simple queue keeps a head index. Instead of removing from index `0`, we remember where the front is. ```text items: [10][20][30][40] head = 0 front = items[head] ``` After one dequeue: ```text items: [10][20][30][40] head = 1 front = items[head] ``` The old value is ignored. No shifting is needed. ## Queue with Head Index Here is a simple integer queue: ```zig const std = @import("std"); const Queue = struct { items: std.ArrayList(i32), head: usize, pub fn init(allocator: std.mem.Allocator) Queue { return Queue{ .items = std.ArrayList(i32).init(allocator), .head = 0, }; } pub fn deinit(self: *Queue) void { self.items.deinit(); } pub fn enqueue(self: *Queue, value: i32) !void { try self.items.append(value); } pub fn dequeue(self: *Queue) ?i32 { if (self.head >= self.items.items.len) return null; const value = self.items.items[self.head]; self.head += 1; return value; } pub fn peek(self: *Queue) ?i32 { if (self.head >= self.items.items.len) return null; return self.items.items[self.head]; } pub fn len(self: *const Queue) usize { return self.items.items.len - self.head; } }; ``` Using it: ```zig pub fn main() !void { var gpa = std.heap.GeneralPurposeAllocator(.{}){}; defer _ = gpa.deinit(); var queue = Queue.init(gpa.allocator()); defer queue.deinit(); try queue.enqueue(10); try queue.enqueue(20); try queue.enqueue(30); while (queue.dequeue()) |value| { std.debug.print("{}\n", .{value}); } } ``` Output: ```text 10 20 30 ``` This queue removes from the front without shifting all elements. ## The Hidden Problem The head-index queue has one issue. After many dequeues, the front moves forward: ```text items: [old][old][old][40][50][60] ^ head ``` The old slots are no longer used, but they still occupy memory. For a long-running queue, you need a cleanup step or a ring buffer. A ring buffer reuses old slots. You will see that in a later section. ## Stack vs Queue in Algorithms Two famous graph algorithms show the difference clearly. Depth-first search uses a stack. It explores one path deeply before coming back. ```text visit A go to B go to C backtrack ``` Breadth-first search uses a queue. It explores nearby nodes first. ```text visit distance 0 visit distance 1 visit distance 2 ``` The collection rule changes the behavior of the algorithm. Same graph, different data structure, different traversal order. ## When to Use a Stack Use a stack when the newest item should be handled first. Good examples: ```text undo operations nested parsing temporary states backtracking depth-first search compiler scopes ``` The rule is simple: ```text last in, first out ``` ## When to Use a Queue Use a queue when the oldest item should be handled first. Good examples: ```text task scheduling message handling network packets breadth-first search print jobs event loops ``` The rule is simple: ```text first in, first out ``` ## Common Beginner Mistakes The first mistake is using `orderedRemove(0)` for a large queue. It works, but it shifts all remaining items every time. The second mistake is popping from an empty stack. Check `items.len` or return an optional. The third mistake is forgetting that `append` can fail because it may allocate. The fourth mistake is exposing too many operations. If you are writing a stack, do not let callers insert into the middle. Wrap the structure and expose only the operations you want. The fifth mistake is keeping pointers into an `ArrayList` while pushing more items. The internal buffer may move during growth. ## A Useful Mental Model A stack is a pile. ```text push 10 push 20 push 30 pop gives 30 ``` A queue is a line. ```text enqueue 10 enqueue 20 enqueue 30 dequeue gives 10 ``` The data structure is mostly about the rule. The rule determines which item gets processed next. ## Summary A stack is last-in, first-out. A queue is first-in, first-out. In Zig, you can build both with `std.ArrayList`. For a stack, append to the end and pop from the end. For a beginner queue, append to the end and remove from the front. For a better queue, keep a head index. For a production queue with long-running reuse, use or build a ring buffer. These structures are small, but they are central to many larger systems.