Stack

What is a stack?

A stack is a linear data structure where you can only add or remove items at one end, called the top.

Think of a pile of plates in a canteen. You put a clean plate on top of the pile, and you take a plate from the top. You never pull a plate out from the middle. The plate that went on last is the first one to come off.

This rule has a name: LIFO — Last In, First Out.

One-line definition: a stack is a collection with two main operations, push (add on top) and pop (remove from top), that follows the LIFO order.

The three operations

Operation	What it does	Plate analogy
push(x)	Puts x on top	Add a plate to the pile
pop()	Removes and returns the top item	Take the top plate
peek() / top()	Returns the top item without removing it	Look at the top plate

Two more helpers are common: isEmpty() and size().

In the 3D model above, the glass box is an array of fixed capacity 7. The small numbers on the left are the array indexes 0…6, and the ← top pointer shows which index is the top. Watch closely: push and pop only ever move that pointer by one.

How it works inside (array version)

We keep an array stack[] and an integer top that stores the index of the top element. An empty stack has top = -1.

Push(x)

1. If top == capacity - 1, the stack is full → Stack Overflow.
2. Otherwise do top = top + 1.
3. Store stack[top] = x.

Pop()

1. If top == -1, the stack is empty → Stack Underflow.
2. Read x = stack[top].
3. Do top = top - 1 and return x.

Notice that we don’t actually erase the old value when popping — we just move top down. The old value is simply ignored and will be overwritten by the next push.

Code

class Stack:
    def __init__(self, capacity):
        self.items = [None] * capacity
        self.capacity = capacity
        self.top = -1                     # empty stack

    def push(self, x):
        if self.top == self.capacity - 1:
            raise OverflowError("Stack Overflow")
        self.top += 1
        self.items[self.top] = x

    def pop(self):
        if self.top == -1:
            raise IndexError("Stack Underflow")
        x = self.items[self.top]
        self.top -= 1
        return x

    def peek(self):
        if self.top == -1:
            raise IndexError("Stack is empty")
        return self.items[self.top]

s = Stack(7)
s.push(12); s.push(45); s.push(7)
print(s.pop())   # 7  (last in, first out)
print(s.peek())  # 45

#include <iostream>
#include <stdexcept>
using namespace std;

class Stack {
    int items[7];
    int top = -1;                         // empty stack
    const int capacity = 7;
public:
    void push(int x) {
        if (top == capacity - 1) throw overflow_error("Stack Overflow");
        items[++top] = x;
    }
    int pop() {
        if (top == -1) throw underflow_error("Stack Underflow");
        return items[top--];
    }
    int peek() {
        if (top == -1) throw underflow_error("Stack is empty");
        return items[top];
    }
};

int main() {
    Stack s;
    s.push(12); s.push(45); s.push(7);
    cout << s.pop() << "\n";   // 7
    cout << s.peek() << "\n";  // 45
}

In real Python code you can simply use a list: append() is push and pop() is pop. In C++ there is std::stack, and in Java ArrayDeque.

Why is everything O(1)?

Push, pop and peek each do a fixed amount of work: one comparison, one change to top, and one array read or write. It doesn’t matter whether the stack holds 5 items or 5 million — the work is the same. That’s constant time, O(1).

Searching for a value is different. The only item you can see is the top, so in the worst case you look at all n items: O(n).

Where are stacks used?

• Undo / Redo in editors: the most recent action is undone first.
• Function calls: when a function calls another, the computer pushes a stack frame and pops it on return. Infinite recursion fills it up → a real stack overflow error!
• Browser back button: pages you visit are pushed; Back pops.
• Checking balanced brackets like {[()]} in compilers.
• Evaluating expressions (postfix / infix conversion).
• Depth-first search (DFS) in graphs.

Common mistakes

• Forgetting to check for underflow before popping.
• Mixing up stack (LIFO) with queue (FIFO). Ask yourself: does the newest item leave first? If yes, it’s a stack.
• Thinking pop “deletes” memory. In the array version it just moves top.