# 5.1 Stacks with an Array

> Last in, first out. The stack ADT (push, pop, peek, isEmpty, isFull) built on a fixed array with a top index, plus overflow and underflow.

Chapter: Stacks & Queues · ~45 min · easy
URL: https://dsa.fetehadin.com/learn/stack-array

## Mental model

Think of a **stack of plates** in the cafeteria. You put a clean plate on **top**, and you take a plate from the **top**. The plate at the bottom was put there first and comes out last. That rule is **LIFO**: Last In, First Out.

A stack is an **ADT**: it is defined by its operations, not by how it is stored.

| Operation | Meaning |
| --- | --- |
| `push(x)` | put x on top |
| `pop()` | remove and return the top item |
| `peek()` / `top()` | look at the top item without removing it |
| `isEmpty()` | is there nothing on the stack? |
| `isFull()` | no room left (array version only) |

### Building it on an array

Keep an array `st[MAX]` and one integer **`top`**, the index of the top item. An empty stack has `top = -1`.

- **push**: `st[++top] = x;` moves top up, then writes.
- **pop**: `return st[top--];` reads, then moves top down.

The old value stays in the array after a pop, but it no longer counts. Only `0..top` is the stack.

### Overflow and underflow

- **Overflow**: push when `top == MAX - 1`. The array has no room.
- **Underflow**: pop when `top == -1`. There is nothing to take.

Always check before you act. These two checks are the most common exam marks on this topic.

### Where stacks show up

Undo/redo, the browser back button, **checking balanced brackets**, evaluating postfix expressions, and the **call stack** that makes recursion work (Chapter 3).

## C++ code: stack-array.cpp

```cpp
#include <iostream>
using namespace std;

const int MAX = 5;

class Stack {
    int st[MAX];
    int top = -1;
public:
    bool isEmpty() const { return top == -1; }
    bool isFull() const { return top == MAX - 1; }
    void push(int x) {
        if (isFull()) { cout << "Overflow! cannot push " << x << "\n"; return; }
        st[++top] = x;
    }
    int pop() {
        if (isEmpty()) { cout << "Underflow!\n"; return -1; }
        return st[top--];
    }
    int peek() const {
        if (isEmpty()) { cout << "Empty!\n"; return -1; }
        return st[top];
    }
};

int main() {
    Stack s;
    for (int i = 1; i <= 6; i++) s.push(i * 10);   // the 6th push overflows
    cout << "peek: " << s.peek() << "\n";
    cout << "pop:  ";
    while (!s.isEmpty()) cout << s.pop() << " ";
    cout << "\n";
    s.pop();                                        // underflow
}
```

Expected output:

```text
Overflow! cannot push 60
peek: 50
pop:  50 40 30 20 10 
Underflow!
```

## Complexity

| Case | Cost |
| --- | --- |
| push | O(1) |
| pop | O(1) |
| peek / isEmpty / isFull | O(1) |
| search for a value | O(n): not a stack operation |

Space: O(MAX), fixed when the array is declared

Every stack operation touches only `st[top]`, so all of them are **O(1)**. The price of an array is a **fixed capacity**.

## Videos

- [Introduction to stack](https://youtu.be/F1F2imiOJfk) (mycodeschool): The stack ADT and LIFO idea with everyday examples, before any code.
- [Array implementation of stacks](https://youtu.be/sFVxsglODoo) (mycodeschool): Builds the array stack in C/C++ with a `top` index, exactly like this page.

## Exam lens

Likely questions:

- Define a stack. Why is it called a LIFO structure?
- Write push and pop for an array stack, including overflow and underflow checks.
- Show the stack after: push 3, push 7, pop, push 2, push 9, pop. What does peek return?
- What does `top = -1` mean? What is the condition for a full stack?
- Give three real applications of a stack.

Common mistakes:

- Writing `st[top++] = x` with `top = -1` (writes to index −1). Use `st[++top] = x`.
- Popping without checking `isEmpty()` (underflow).
- Pushing without checking `isFull()` (writes past the array).
- Thinking `pop` must erase the value. Moving `top` down is enough.

## Quick check

1. Start empty. push 4, push 8, pop, push 1, push 6, pop. What is on top?
   A. 4
   B. 8
   C. 1
   D. 6
   Answer: C. Stack after each step - [4], [4,8], [4], [4,1], [4,1,6], [4,1]. The top is 1.

2. With `int st[MAX]; int top = -1;` the stack is full when…
   A. `top == MAX`
   B. `top == MAX - 1`
   C. `top == 0`
   D. `top == -1`
   Answer: B. The last valid index is MAX − 1.

3. Popping from an empty stack is called…
   A. overflow
   B. underflow
   C. a memory leak
   D. a segmentation fault, always
   Answer: B. Underflow. Overflow is pushing onto a full stack.

4. Which of these naturally uses a stack?
   A. A printer queue
   B. The undo button
   C. A ticket line
   D. Round-robin scheduling
   Answer: B. Undo reverses the most recent action first. The other three are first-come, first-served (queues).

## Practice

**Trace by hand.** MAX = 3. Do push 5, push 2, push 8, push 1, pop, pop, peek, pop, pop. Write the array, `top`, and anything printed after each step.

Solution:

- push 5 → `[5]`, top 0
- push 2 → `[5,2]`, top 1
- push 8 → `[5,2,8]`, top 2 (now full)
- push 1 → **Overflow**, nothing changes
- pop → returns 8, top 1
- pop → returns 2, top 0
- peek → 5
- pop → returns 5, top −1
- pop → **Underflow**


**Implement it.** Use your array stack to reverse a string, and to print a number in binary (push `n % 2`, then pop everything).

Hint: Push every character, then pop them all. The last one in is the first one out, so the order flips.

```cpp
string reverseStr(const string& s) {
    char st[100]; int top = -1;
    for (char c : s) st[++top] = c;
    string r;
    while (top != -1) r += st[top--];
    return r;
}
```


**Problems:**

- [Valid Parentheses](https://leetcode.com/problems/valid-parentheses/) (easy). Hint: Push opening brackets. On a closing bracket the top must be its partner. At the end the stack must be empty.
- [Backspace String Compare](https://leetcode.com/problems/backspace-string-compare/) (easy). Hint: Build each string with a stack. `#` means pop (if not empty). Compare the results.
- [Evaluate Reverse Polish Notation](https://leetcode.com/problems/evaluate-reverse-polish-notation/) (medium). Hint: Numbers are pushed. An operator pops b, then a, and pushes a op b. Order matters for − and /.

## Mastery checklist

- [ ] I can explain LIFO with a real example.
- [ ] I can write push, pop, peek, isEmpty and isFull for an array stack.
- [ ] I can trace a sequence of stack operations by hand.
- [ ] I always check for overflow before push and underflow before pop.