=========================================================
SUBJECT: CS103 - Abstract Data Types
TOPIC: The Stack (LIFO)
=========================================================
### 1. WHAT IS A STACK?
A Stack is an Abstract Data Type (ADT) that serves as a collection of elements,
with two principal operations: `Push`, which adds an element to the collection, and
`Pop`, which removes the most recently added element.
This behavior is known as **LIFO (Last-In, First-Out)**. Think of it like a stack
of plates: you add a new plate to the top, and you also remove a plate from the
top.
### 2. CORE OPERATIONS
* **Push:** Add an element to the top of the stack.
* **Pop:** Remove the element from the top of the stack and return it.
* **Peek (or Top):** Look at the element at the top of the stack without removing
it.
* **isEmpty:** Check if the stack is empty.
### 3. IMPLEMENTATION & COMPLEXITY
A stack can be easily implemented using either an **Array** or a **Linked List**.
| Operation | Time Complexity (Array/Linked List) | Explanation
|
|-----------------|-------------------------------------|--------------------------
---------------------------------|
| Push | O(1) | Add to the end of the
array or head of the linked list. |
| Pop | O(1) | Remove from the end of
the array or head of the list. |
| Peek / Top | O(1) | Access the last element
or the head node. |
| Search | O(N) | This operation violates
the stack principle but is possible. |
**Space Complexity:** O(N) for storing N elements.
### 4. COMMON USE CASES
* **Function Call Management:** The "call stack" keeps track of active function
calls in a program.
* **Undo/Redo Functionality:** Each action is pushed onto a stack. "Undo" pops the
action.
* **Expression Evaluation:** Converting infix expressions to postfix (e.g., `3 + 4`
to `3 4 +`) and evaluating them.
* **Syntax Parsing:** Used in compilers to check for balanced parentheses and
braces.
* **Backtracking Algorithms:** Such as solving a maze or in depth-first search
(DFS).
