Stack

Prerequisites

• Arrays and indices.
• Structs in C.
• The idea of "the most recent" item.

The analogy

How it works

Start with a sequence of operations by hand

Start with an empty stack. The array version keeps top, the index of the top item (−1 when empty). Predict, then open "Check".

Finish the picture: matching brackets

Check "([])": push every open bracket; at a close bracket, pop and check it matches.

• ( [ ]. Predict the stack after reading these three characters.
  Check

  Push (, push [, then ] pops [, a match. The stack is [(].

• The final ). Predict the result.
  Check

  It pops (, a match. The stack is empty at the end, so the string is balanced.

The rule in plain words

Keep the items in an array and an index top (−1 when empty). push: increase top, store. pop: read at top, decrease it. peek: read at top only.

Only the top is ever touched, so every operation is a constant amount of work.

The code

Read this code after you have done the operations by hand. It will make more sense.

typedef struct { int data[100]; int top; } Stack;    /* top = -1 when empty */

void push(Stack *s, int v)    { s->data[++s->top] = v; }    /* caller checks top < 99 */
int  pop(Stack *s)            { return s->data[s->top--]; } /* caller checks !is_empty */
int  peek(const Stack *s)     { return s->data[s->top]; }
int  is_empty(const Stack *s) { return s->top == -1; }

int balanced(const char *s) {                /* "([])" -> 1, "([)]" -> 0 */
    char st[100]; int top = -1;
    for (int i = 0; s[i]; i++) {
        char c = s[i];
        if (c == '(' || c == '[') st[++top] = c;
        else if (c == ')' || c == ']') {
            char want = c == ')' ? '(' : '[';
            if (top < 0 || st[top--] != want) return 0;   /* nothing open, or wrong kind */
        }
    }
    return top == -1;                         /* every bracket was closed */
}

flowchart TD
  A["read next character"] --> B{"open bracket?"}
  B -->|yes| C["push it"]
  B -->|no| D{"close bracket?"}
  D -->|yes| E{"stack empty or top doesn't match?"}
  E -->|yes| F["not balanced"]
  E -->|no| G["pop"]
  C --> A
  G --> A
  D -->|"no more characters"| H{"stack empty?"}
  H -->|yes| I["balanced"]
  H -->|no| F
          

How fast is it?

Each operation touches only the top slot. For a string of $n$ characters, the bracket check does at most one push and one pop per character:

Common mistakes

• Popping without checking that the stack is non-empty.
• Confusing stack and queue order: a stack returns the newest item.
• Forgetting to check that the stack is empty at the end of the bracket check: "((" must fail.

Try it yourself

Did you know?

Key points to remember

If you remember one thing from each line, remember the because.

• The last item pushed is the first popped because both push and pop work at the same end, the top.
• Every operation is $O(1)$ because only the top slot is ever read or written.
• Bracket matching works because the most recent unclosed bracket is always the one that must close next.
• Underflow and overflow must be checked because the array has fixed bounds.
• Recursion uses a stack because the most recent call must finish first.

Self-check questions

Answer these in order, out loud. They follow the page, so your answers become the script of your video.

1. How is a stack like a pile of plates?
   Sample answer

   You add and remove plates only at the top, so the last plate added is the first one taken.

2. Walk through push 5, push 3, pop, push 8, peek.
   Sample answer

   After the pushes the stack is [5, 3]; pop returns 3, leaving [5]; push 8 gives [5, 8]; peek returns 8 without removing it.

3. Why does push use ++s->top but pop uses s->top--?

   A good answer says when top changes relative to the read or write.

   Sample answer

   push must move to the next free slot before writing; pop must read the current top before moving down. Prefix and postfix give exactly those orders.

4. So what is a stack, in one sentence?
   Sample answer

   A last-in, first-out collection where you push and pop only at the top.

5. Why does a stack solve bracket matching?

   A good answer mentions the most recent open bracket.

   Sample answer

   A closing bracket must match the most recent unclosed opening bracket, and the stack's top is exactly that bracket.

6. What do push, pop, peek and search cost?
   Sample answer

   push, pop and peek are $O(1)$; searching for an arbitrary value is $O(n)$, but that isn't a stack operation.

7. What happens if you pop an empty stack, and how do you prevent it?
   Sample answer

   It reads outside the array (underflow). Check is_empty before popping and report an error instead.

8. If you had to teach this to a friend in 2 minutes, what would you leave out, and why?
   Sample answer

   I'd leave out the postfix example and the ++top details. I'd keep the plate analogy, push 5, push 3, pop → 3, and "LIFO, everything $O(1)$, used for undo and brackets".

External resources

• VisuAlgo: Stack: choose "Stack" and animate push and pop.
• GeeksforGeeks: Stack data structure: array and linked-list versions with applications.
• Wikipedia: Stack: history and uses such as the call stack.

Videos

• YouTube search: stack and balanced parentheses: pick a walkthrough of the bracket check.