Stack: quick revision, 14 bites

Stack: LIFO Principle

Last in, first out—the core rule.

A **stack** is a linear data structure that follows the **LIFO** (Last-In, First-Out) principle. The most recently added element is the first one to be removed. Think of a stack of plates: you add and remove from the top only.

Takeaway. Stacks enforce LIFO: the last element added is the first removed.

Core Stack Operations

Push, pop, peek—the big three.

Takeaway. Push adds, pop removes, peek inspects—all at the top.

Stack Time Complexities

All operations are O(1).

In a well-implemented stack (using an array or linked list), **push**, **pop**, and **peek** all run in **O(1)** time. This makes stacks extremely efficient for their intended use.

Takeaway. Stack operations are constant-time, O(1).

Real-World Stack Examples

Stacks are everywhere in computing.

Takeaway. Stacks power undo, browser navigation, and function calls.

Function Call Stack

How recursion is managed.

When a function is called, its context (local variables, return address) is **pushed** onto the call stack. When the function returns, that context is **popped**. This is why recursion uses stack memory and can cause stack overflow if too deep.

Takeaway. The call stack manages function calls via push and pop.

Stack in Action: Browser Back Button

Click back? That's a pop.

As you visit pages, each URL is **pushed** onto a stack. Clicking 'Back' **pops** the current page and reveals the previous one. The order is always LIFO—your most recent page is the first to go.

Takeaway. Browser navigation uses a stack to track page history.

Implementing a Stack in Python

Simple list-based stack.

Takeaway. Python lists can act as stacks using append() and pop().

Stack Size Formula

Know your stack's capacity.

Takeaway. Stack size = top index + 1.

Checking Balanced Parentheses

A classic stack application.

Takeaway. Stacks elegantly solve balanced parentheses checking.

Popping from an Empty Stack

Underflow is a real bug.

Takeaway. Always check for empty before pop/peek.

Choosing Stack Implementation

Array vs. linked list.

Takeaway. Use array-based for simplicity and cache, linked-list for dynamic size.

Stack in Expression Evaluation

Postfix? Use a stack.

In exams, you may be asked to evaluate a **postfix** expression. Use a stack: push operands, and when you see an operator, pop two operands, apply the operator, and push the result.

Takeaway. Postfix evaluation is a classic stack application.

Remember LIFO with Plates

Plates on a spring holder.

Visualize a **spring-loaded stack of plates** in a cafeteria. You always take the top plate (last placed), and new plates are added on top. That's LIFO.

Takeaway. LIFO = like a stack of plates.

Stack Overflow Origin

The name comes from stacks.

The popular programming Q&A site **Stack Overflow** gets its name from the common error that occurs when a program's call stack exceeds its memory limit—a fitting name for a site that helps fix such errors.

Takeaway. Stack Overflow is named after the call stack error.