š Stack - LIFO Data Structure
š¢ Beginner Linear DS 45 min read
šÆ What is a Stack?
A Stack is a linear data structure that follows the LIFO (Last In, First Out) principle. Think of a stack of plates: you can only take the top plate. The last plate placed is the first one removed.
š Stack Visualization
ā push("C")
| C | ā top ā pop() ā "C"
| B | | B | ā new top
| A | | A |
+---+ +---+š Core Operations
- push(x): Add element to top - O(1)
- pop(): Remove & return top element - O(1)
- peek()/top(): View top element - O(1)
- isEmpty(): Check if empty - O(1)
- size(): Number of elements - O(1)
š» PHP Implementation
<?php
class Stack {
private array $items = [];
public function push(mixed $item): void {
$this->items[] = $item; // O(1) amortized
}
public function pop(): mixed {
if ($this->isEmpty()) {
throw new UnderflowException('Stack is empty');
}
return array_pop($this->items); // O(1)
}
public function peek(): mixed {
if ($this->isEmpty()) {
throw new UnderflowException('Stack is empty');
}
return $this->items[count($this->items) - 1];
}
public function isEmpty(): bool {
return empty($this->items);
}
public function size(): int {
return count($this->items);
}
}
// Usage
$stack = new Stack();
$stack->push(10);
$stack->push(20);
$stack->push(30);
echo $stack->pop(); // 30
echo $stack->peek(); // 20
echo $stack->size(); // 2š Key Applications
š Undo/Redo
Text editors, Photoshop. Each action is pushed. Undo pops the stack.
š Browser History
Back button. Each page visit is pushed. Back pops to previous page.
{([])} Balance
Check balanced parentheses/brackets in code editors.
š Function Calls
Call stack in programming languages. Each function call is pushed.
š Expression Evaluation
Infix ā Postfix conversion, evaluating math expressions.
š³ DFS Traversal
Depth-First Search in trees/graphs uses a stack (or recursion).
Example: Balanced Parentheses
function isBalanced(string $expr): bool {
$stack = [];
$pairs = [')' => '(', '}' => '{', ']' => '['];
for ($i = 0; $i < strlen($expr); $i++) {
$c = $expr[$i];
if (in_array($c, ['(', '{', '['])) {
$stack[] = $c; // push opening bracket
} elseif (isset($pairs[$c])) {
if (empty($stack) || array_pop($stack) !== $pairs[$c]) {
return false; // mismatch
}
}
}
return empty($stack); // all brackets matched
}
var_dump(isBalanced("({[]})")); // true
var_dump(isBalanced("({[})")); // falseš PHP Built-in: SplStack
$stack = new SplStack(); // extends SplDoublyLinkedList
$stack->push('A');
$stack->push('B');
$stack->push('C');
echo $stack->pop(); // C (LIFO)
echo $stack->top(); // Bš¼ Interview Questions
Use
array_push() for push and array_pop() for pop. Both are O(1). Track top with count()-1.Use two stacks: main stack + min stack. When pushing, also push min(current, newVal) to min stack. getMin() peeks min stack. All O(1).
Push: O(1) - enqueue to Q1. Pop: O(n) - dequeue all but last from Q1 to Q2, dequeue last (the pop value), swap Q1āQ2.