Stacks: LIFO Operations, Array/List Implementations & Bracket Matching0%
Stacks: LIFO Operations, Array/List Implementations & Bracket Matching
Beginner12 min read•Updated: Jul 11, 2026
Stacks: LIFO Operations, Array/List Implementations & Bracket Matching
A Stack is a linear data structure governed strictly by the LIFO (Last In, First Out) principle. The last element added to the stack is the first element to be removed. Stacks power fundamental computing mechanisms: the browser back-button history, text editor undo/redo, expression evaluation, and compiler function call stacks.
1. Real-World Analogy: The Spring-Loaded Plate Dispenser
Think of the plate stack dispenser in a university cafeteria:
- When a dishwasher adds clean plates, they are placed on the top of the stack (Push).
- When a hungry student takes a plate, they take the plate from the top (Pop).
- You cannot access the plate at the bottom without first removing every plate above it!
2. The Core Stack Operations
Click to Zoom| Operation | Action | Time Complexity |
|---|---|---|
push(val) | Adds an element to the top of the stack | $O(1)$ |
pop() | Removes and returns the top element | $O(1)$ |
peek() / top() | Views the top element without removing it | $O(1)$ |
isEmpty() | Checks if the stack contains zero elements | $O(1)$ |
3. Classic Problem: Valid Parentheses & Bracket Matching
Given a string s containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid:
- 1Open brackets must be closed by the same type of brackets.
- 2Open brackets must be closed in the correct order.
The Stack Solution:
- When encountering an opening bracket (
(,{,[), push its corresponding closing bracket onto the stack. - When encountering a closing bracket, pop from the stack. If the popped bracket does not match or the stack is empty, the string is invalid!
- If the stack is empty at the end, all brackets were matched successfully.
4. Multi-Language Implementations: Valid Parentheses
Python 3:
Python
def is_valid_parentheses(s: str) -> bool:
stack = []
bracket_map = {')': '(', '}': '{', ']': '['}
for char in s:
if char in bracket_map.values():
# Opening bracket: push to stack
stack.append(char)
elif char in bracket_map:
# Closing bracket: check stack
if not stack or stack[-1] != bracket_map[char]:
return False
stack.pop()
else:
continue # Non-bracket character
return len(stack) == 0
Modern JavaScript / TypeScript:
TypeScript
export function isValidParentheses(s: string): boolean {
const stack: string[] = [];
const map: Record<string, string> = {
')': '(',
'}': '{',
']': '['
};
for (let i = 0; i < s.length; i++) {
const char = s[i];
if (char === '(' || char === '{' || char === '[') {
stack.push(char);
} else if (char in map) {
if (stack.length === 0 || stack[stack.length - 1] !== map[char]) {
return false;
}
stack.pop();
}
}
return stack.length === 0;
}
5. Step-by-Step Trace: s = "{ [ ] ( ) }"
| Char | Type | Stack Before | Action | Stack After | Status |
|---|---|---|---|---|---|
{ | Open | [] | Push { | ['{'] | Valid |
[ | Open | ['{'] | Push [ | ['{', '['] | Valid |
] | Close | ['{', '['] | Pop matches [ | ['{'] | Valid |
( | Open | ['{'] | Push ( | ['{', '('] | Valid |
) | Close | ['{', '('] | Pop matches ( | ['{'] | Valid |
} | Close | ['{'] | Pop matches { | [] | Valid |
End State: Stack is empty [] $\to$ Valid Parentheses (True)!
Interactive Quiz
Multiple Choice Questions
Question 1
Which fundamental access principle dictates how elements enter and leave a Stack?
Question 2
What is the time complexity of the
push() and pop() operations on a properly implemented Stack?Question 3
What does it mean when calling
pop() on an empty stack results in a "Stack Underflow"?Question 4
Why is a Stack the natural data structure for evaluating nested parentheses like
({[]})?Question 5
In software architecture, which component relies directly on a stack data structure to manage function calls and local execution scope?
Next Lesson
Monotonic Stacks: Next Greater Element & Histogram Area Patterns
Continue learning with hands-on practice, examples, and exercises in the upcoming topic.
Related Lessons
Practice Quiz
Test your understanding of this lesson with 5 questions. Each question has one correct answer.