stack data structure: quick revision, 19 bites

What is a Stack?

Last in, first out — the core rule.

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

Takeaway. A stack is a LIFO structure where all operations happen at the top.

Stack Operations

The five essential stack operations.

Takeaway. Stacks support push, pop, peek, isEmpty, and size operations.

Plate Stacker Analogy

Plates: you can only touch the top.

Imagine a spring-loaded plate dispenser in a cafeteria. You place plates on top (push) and take the top plate off (pop). You never access plates in the middle. This is exactly how a stack works.

Takeaway. The plate dispenser perfectly models stack LIFO behavior.

Stack in Action

Push 1,2,3 then pop — what order?

Start with an empty stack. Perform: push(1), push(2), push(3), pop(), pop(), push(4), pop().

Takeaway. Pop always removes the most recently pushed element.

Time Complexity of Stack Operations

All operations are O(1) — constant time.

Takeaway. Stack operations are O(1) when implemented with arrays or linked lists.

Confusing Stack with Queue

LIFO vs FIFO — don't mix them!

Takeaway. Stacks are LIFO; queues are FIFO. Remember the difference.

Real-World Stack Applications

Stacks are everywhere in computing.

Takeaway. Stacks power undo, back buttons, recursion, and expression parsing.

Implementing a Stack in Python

Simple Python stack using a list.

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

How to Check Balanced Parentheses

Use a stack to match brackets.

Takeaway. Stacks elegantly solve balanced parentheses problems.

When to Use a Stack

Need LIFO? Use a stack.

Takeaway. Choose a stack when LIFO order is required.

Remember LIFO with a Pile of Books

Last book on top comes off first.

Visualize a pile of books. The last book you placed on top is the first one you remove. That's LIFO. Remember: **L**ast **I**n **F**irst **O**ut.

Takeaway. LIFO = last book placed is first removed.

Exam Tip: Trace Stack Operations Carefully

Always draw the stack state.

In exams, when asked to trace a sequence of push/pop operations, draw the stack as a vertical list. Mark the top clearly. This avoids mistakes and helps you answer quickly.

Takeaway. Drawing the stack state prevents errors in tracing.

Function Call Stack

Every function call uses a stack.

When a program calls a function, the system pushes the return address and local variables onto the call stack. When the function returns, that frame is popped. This is why recursion can cause stack overflow if too deep.

Takeaway. The call stack is a real-world stack used by every program.

Stack Overflow

Too many pushes can crash your program.

If you push more elements than the stack can hold (e.g., in a fixed-size array implementation), you get **stack overflow**. In recursion, infinite recursion leads to stack overflow. Always check capacity or use dynamic structures.

Takeaway. Stack overflow occurs when pushing beyond capacity or infinite recursion.

Array vs Linked List Stack

Two ways to implement a stack.

Takeaway. Both give O(1) operations; choose based on memory and flexibility needs.

Expression Evaluation with Stacks

Convert infix to postfix using stacks.

Stacks are used to convert infix expressions (e.g., `A + B * C`) to postfix (e.g., `A B C * +`) and to evaluate postfix expressions. Operators are pushed and popped based on precedence.

Takeaway. Stacks are essential for parsing and evaluating arithmetic expressions.

Stack Implementation in C++

Using std::stack in C++.

Takeaway. C++ provides std::stack with push, pop, top, and empty methods.

Forgetting to Check Empty Before Pop

Popping an empty stack causes errors.

In many implementations, popping from an empty stack throws an exception or causes undefined behavior. Always check `isEmpty()` before calling `pop()` or `peek()`.

Takeaway. Always verify the stack is not empty before pop or peek.

Stack Recap

Everything you need to remember.

Takeaway. Stacks are simple, efficient, and widely used.