Stack

What is a Stack?

A Stack is an abstract, linear data structure that operates under the LIFO (Last In, First Out) principle. This means the last element inserted into the stack will be the first one to be removed.

Think of it like a physical stack of dinner plates in a cafeteria: you can only place a new plate on the top (Push), and you can only take the top plate off (Pop). If you want to access the bottom plate, you must first remove all plates stacked above it.

---

Memory Layout & Implementations

A Stack can be implemented in two primary ways:

1. Array-Based Implementation (Contiguous)

Uses a static or dynamic array. A pointer or integer variable named top keeps track of the index of the highest element.

• Pros: Fast O(1) operations, cache-friendly due to contiguous memory.
• Cons: Size is limited (static array) or requires costly resizing/doubling (dynamic array).

2. Linked List-Based Implementation (Dynamic)

Uses nodes linked by pointers where the top element is always the head node of the list.

• Pros: Dynamic sizing; only limited by system memory.
• Cons: Pointer overhead (O(N) extra memory for pointers) and less cache-friendly due to memory fragmentation.

---

Core Operations

Operation	Description	Time Complexity
Push	Add an element to the top of the stack	O(1)
Pop	Remove and return the top element	O(1)
Peek / Top	Access the top element without removing it	O(1)
IsEmpty	Check if the stack contains zero elements	O(1)
IsFull	Check if the stack has reached capacity (for fixed-size arrays)	O(1)

---

Real-World Applications

Stacks are fundamental in system-level software and classic algorithms:

• Function Call Stack: The CPU uses a stack to manage active subroutines, tracking return addresses and local variables during nested or recursive execution.
• Undo / Redo Mechanisms: Text editors, graphics tools, and web browsers use double stacks to track edit histories, allowing actions to be undone or redone.
• Expression Evaluation & Parsing: Compilers use stacks to evaluate arithmetic expressions and parse matching nested delimiters (brackets, HTML tags).
• Backtracking Algorithms: Depth-First Search (DFS) on graphs/trees uses a stack (either the system recursion stack or an explicit stack object) to backtrack to previous nodes.

---

Interview Tips 💡

1. Check for Boundary Conditions: Always guard against Stack Underflow (popping from an empty stack) and Stack Overflow (pushing to a full stack).
2. Dynamic Resizing: If an interviewer asks about array-based implementations, discuss amortized O(1) insertion using array-doubling.
3. Dual Stacks: Consider using two stacks to solve special problems, such as implementing a Queue, or tracking the minimum element in O(1) time (Min Stack).