Stack Basics: quick revision, 14 bites

Stack: LIFO Principle

Last in, first out!

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 LIFO: the most recent addition is the first to be removed.

Core Stack Operations

Four essential operations.

The primary operations are **push** (insert), **pop** (delete), **peek** (top element), and **isEmpty** (check if empty). Some implementations also include **isFull** for fixed-size arrays.

Takeaway. Push, pop, peek, and isEmpty are the fundamental stack operations.

Stack of Plates Analogy

Plates in a cafeteria.

Imagine a spring-loaded stack of plates in a cafeteria. You always take the top plate (pop) and add new plates on top (push). You never access plates from the bottom or middle directly.

Takeaway. The plate stack is a perfect real-world model of LIFO behavior.

Array-Based Stack Design

Use an array and a top index.

In an **array implementation**, we use a fixed-size array and a variable `top` that points to the index of the top element. Initially, `top = -1` (empty stack).

Takeaway. Array stack uses a top index to track the top element; push/pop adjust this index.

Array Stack in C++

Code it in C++.

Takeaway. A simple C++ class demonstrates push, pop, peek, and isEmpty with an array.

Time Complexity of Operations

All O(1) — constant time.

All stack operations (push, pop, peek, isEmpty) run in **O(1)** time because they only involve the top index and a single array slot. No shifting or searching is needed.

Takeaway. Array stack operations are O(1), making them highly efficient.

Forgetting Overflow/Underflow

Check bounds before push/pop.

A common mistake is not checking if the stack is full before push or empty before pop. This leads to **overflow** (writing beyond array) or **underflow** (reading invalid index).

Takeaway. Always check for overflow and underflow to avoid runtime errors.

Real-World Stack Uses

Stacks are everywhere.

Takeaway. Stacks power recursion, undo features, and expression parsing.

Array vs Linked List Stack

Fixed vs dynamic size.

Takeaway. Array stacks are simpler and cache-friendly but fixed-size; linked lists are flexible.

Choosing Array Stack

When to use array stack.

Takeaway. Array stacks are ideal for fixed-size, performance-critical scenarios.

Remember LIFO in Exams

LIFO is the key.

In exams, always identify the order of operations. For a sequence of pushes and pops, simulate step-by-step. Remember: the last pushed element is the first popped.

Takeaway. Simulate push/pop sequences carefully to avoid mistakes.

LIFO = Last In, First Out

Think of a stack of books.

Visualize a stack of books: you can only remove the top book. The last book placed is the first removed. That's LIFO.

Takeaway. LIFO is like a book stack — top only.

Call Stack in Programming

Your code uses a stack.

Every time a function calls another, the system uses a **call stack** to store return addresses and local variables. When a function returns, its frame is popped.

Takeaway. Function calls rely on a stack behind the scenes.

Top Index Relationship

Top = size - 1.

Takeaway. Top index directly reflects the number of elements.