4. Stacks

🧸 ELI5: A stack is a stack of pancakes. You can only add a pancake to the top, and you can only eat from the top. You can never grab the bottom pancake without removing all the ones above it first. Last one in, first one out (LIFO).

🌍 Real life: The "Undo" button (Ctrl+Z) — it undoes your most recent action first. Your browser's "Back" button. A stack of trays in a cafeteria.

📝 Pseudocode:

stack = []
push(stack, "plate1")
push(stack, "plate2")
pop(stack)   // removes "plate2" (the last one added)

🐹 Go:

package main

import "fmt"

type Stack struct {
	items []string
}

func (s *Stack) Push(item string) {
	s.items = append(s.items, item)
}

func (s *Stack) Pop() (string, bool) {
	if len(s.items) == 0 {
		return "", false
	}
	last := s.items[len(s.items)-1]
	s.items = s.items[:len(s.items)-1]
	return last, true
}

func main() {
	undoHistory := &Stack{}
	undoHistory.Push("typed 'hello'")
	undoHistory.Push("typed 'world'")
	action, _ := undoHistory.Pop()
	fmt.Println("undo:", action) // undo: typed 'world'
}

🇨 C (a fixed-capacity array-backed stack — no dynamic growth needed for a stack of pancakes):

#include <stdio.h>
#include <string.h>

#define STACK_CAP 32

typedef struct {
    char items[STACK_CAP][64];
    int  top; // -1 means empty
} Stack;

void stack_push(Stack *s, const char *item) {
    if (s->top + 1 >= STACK_CAP) return;
    strncpy(s->items[++s->top], item, sizeof s->items[0] - 1);
}

int stack_pop(Stack *s, char *out, size_t out_cap) {
    if (s->top < 0) return 0;
    strncpy(out, s->items[s->top--], out_cap - 1);
    return 1;
}

int main(void) {
    Stack undoHistory = { .top = -1 };
    stack_push(&undoHistory, "typed 'hello'");
    stack_push(&undoHistory, "typed 'world'");

    char action[64];
    if (stack_pop(&undoHistory, action, sizeof action)) {
        printf("undo: %s\n", action); // undo: typed 'world'
    }
    return 0;
}

⏱️ Complexity: Push/Pop = O(1) — always fast, no matter how tall the stack.