Stack

A stack is a linear data structure that follows the LIFO (Last In, First Out) principle — the element inserted most recently is the first one to be removed. Think of a stack of plates: you place new plates on top and also take plates from the top.

Key Terminology

• LIFO — Last In, First Out: the defining property of a stack.
• Top — the position in the stack where insertion and deletion happen.
• Push — operation to INSERT an element onto the top of the stack.
• Pop — operation to REMOVE and return the element from the top.
• Peek / Top — VIEW the top element without removing it.
• isEmpty — check whether the stack has no elements.
• Overflow — attempting to push onto a full stack (relevant for array-based fixed stacks).
• Underflow — attempting to pop from an empty stack.

Stack as a Python List

Python lists can be used directly as stacks:

• Push: list.append(element)
• Pop: list.pop() — removes and returns the last element
• Peek: list[-1] — accesses the last element without removing
• isEmpty: len(list) == 0

```
stack = []
stack.append(10) # push 10
stack.append(20) # push 20
stack.append(30) # push 30
print(stack.pop()) # pop → 30
print(stack[-1]) # peek → 20
```

State after pushes: [10, 20, 30] — top is 30.

Stack Operations — Step-by-Step

| Operation | Stack State (left=bottom, right=top) |
|-----------|--------------------------------------|
| Initial | [] |
| push(5) | [5] |
| push(10) | [5, 10] |
| push(15) | [5, 10, 15] |
| pop() returns 15 | [5, 10] |
| peek() returns 10 | [5, 10] (unchanged) |
| pop() returns 10 | [5] |

Applications of Stack

1. 1.Function call management — The OS uses a call stack to track function calls and return addresses.
2. 2.Expression evaluation — Evaluating postfix (Reverse Polish Notation) expressions.
3. 3.Infix to Postfix conversion — Uses a stack to handle operator precedence.
4. 4.Undo / Redo — Text editors use stacks to track changes.
5. 5.Balanced parentheses checking — Verifying that brackets are properly matched.
6. 6.Backtracking — Navigation in web browsers (back button), maze solving.
7. 7.Reversing a string / sequence — Push all characters, then pop them.

Infix, Prefix, and Postfix Notation

• Infix: operator between operands — A + B
• Prefix (Polish): operator before operands — + A B
• Postfix (Reverse Polish): operator after operands — A B +

1. 1.Postfix is evaluated using a stack:
2. 2.Scan left to right.
3. 3.If operand: push onto stack.
4. 4.If operator: pop two operands, apply operator, push result.

• Popping from an empty stack — always check isEmpty() before calling pop() to avoid IndexError.
• Confusing push/pop direction — insertion and deletion BOTH happen at the TOP (same end).
• Using insert(0,...) or pop(0) — this is a queue operation, not a stack operation.

A stack is a LIFO structure supporting push, pop, peek, and isEmpty operations. In Python, a list with append() and pop() serves as an efficient stack. Stacks are used extensively in expression evaluation, function calls, balanced parenthesis checking, and backtracking algorithms.