# Stack
A **stack** is a last-in, first-out (LIFO) sequence. The only accessible element is the top; you push to add and pop to remove, always at the same end. A stack can be implemented over an [[array]] (with a top index) or a [[linked-list]] (with insertions at the head). The array-backed version is more cache-friendly; the linked version avoids a fixed capacity.

```c
// array-backed stack
struct stack {
    int data[MAX];
    int top;
};

void push(struct stack *s, int val) { s->data[s->top++] = val; }
int  pop (struct stack *s)          { return s->data[--s->top]; }
int  peek(struct stack *s)          { return s->data[s->top - 1]; }
```

The canonical uses are those where the last thing encountered is the first thing resolved: function call frames (each call pushes a frame; return pops it), expression evaluation and parsing (matching parentheses, operator precedence in the shunting-yard algorithm), depth-first search, and undo history.

The CPU's hardware call stack is a stack in the exact same sense: `CALL` pushes the return address and `RET` pops it. Understanding this makes stack overflows — pushing too many frames before any return — straightforward to diagnose.

| Operation | Time |
|---|---|
| Push | O(1) |
| Pop | O(1) |
| Peek | O(1) |
| Search | O(n) |