Stack (Ngăn Xếp): Cấu Trúc Dữ Liệu LIFO Quan Trọng Trong Lập Trình¶
Stack (ngăn xếp) là một trong những cấu trúc dữ liệu cơ bản và quan trọng nhất trong lập trình. Trong bài viết này, chúng ta sẽ cùng tìm hiểu chi tiết về Stack từ khái niệm cơ bản, cách hoạt động, triển khai, cho đến các ứng dụng thực tế.
1. Stack là gì?¶
1.1. Định nghĩa¶
Stack là một cấu trúc dữ liệu tuyến tính hoạt động theo nguyên tắc LIFO (Last In, First Out - vào sau, ra trước). Điều này có nghĩa là phần tử được thêm vào cuối cùng sẽ là phần tử đầu tiên bị loại bỏ.
1.2. Hình dung Stack¶
Bạn có thể tưởng tượng Stack như:
- Một chồng đĩa: Bạn chỉ có thể đặt đĩa lên trên cùng và chỉ có thể lấy đĩa từ trên xuống.
- Một ống thẳng: Chỉ có một đầu để cho vào và lấy ra.
- Một chồng sách: Quyển sách được đặt lên sau cùng sẽ được lấy ra đầu tiên.
┌─────────┐
│ 4 │ ← Top (đỉnh stack)
├─────────┤
│ 3 │
├─────────┤
│ 2 │
├─────────┤
│ 1 │ ← Bottom (đáy stack)
└─────────┘
2. Các Thao Tác Cơ Bản của Stack¶
Stack hỗ trợ ba thao tác chính, tất cả đều có độ phức tạp O(1):
2.1. Push (Đẩy vào)¶
- Chức năng: Thêm một phần tử vào đỉnh của stack
- Độ phức tạp: O(1)
2.2. Pop (Lấy ra)¶
- Chức năng: Loại bỏ và trả về phần tử ở đỉnh stack
- Độ phức tạp: O(1)
2.3. Peek/Top (Xem đỉnh)¶
- Chức năng: Xem phần tử ở đỉnh stack mà không loại bỏ nó
- Độ phức tạp: O(1)
3. Triển Khai Stack Bằng Dynamic Array¶
3.1. Tại sao sử dụng Dynamic Array?¶
Stack có thể được triển khai bằng dynamic array vì:
- Thao tác thêm/xóa ở cuối mảng là O(1)
- Dynamic array tự động mở rộng khi cần
- Đơn giản và hiệu quả
3.2. Code Implementation trong Python¶
class Stack:
def __init__(self):
"""Khởi tạo stack rỗng"""
self.items = [] # Sử dụng list (dynamic array) của Python
def push(self, item):
"""Thêm phần tử vào đỉnh stack"""
self.items.append(item)
print(f"Pushed {item} onto stack")
def pop(self):
"""Loại bỏ và trả về phần tử ở đỉnh stack"""
if self.is_empty():
raise IndexError("pop from empty stack")
item = self.items.pop()
print(f"Popped {item} from stack")
return item
def peek(self):
"""Xem phần tử ở đỉnh stack mà không loại bỏ"""
if self.is_empty():
raise IndexError("peek from empty stack")
return self.items[-1]
def is_empty(self):
"""Kiểm tra stack có rỗng không"""
return len(self.items) == 0
def size(self):
"""Trả về số lượng phần tử trong stack"""
return len(self.items)
def display(self):
"""Hiển thị stack theo chiều dọc"""
if self.is_empty():
print("Stack is empty")
return
print("Stack (top to bottom):")
for i in range(len(self.items) - 1, -1, -1):
symbol = "← TOP" if i == len(self.items) - 1 else ""
print(f"│ {self.items[i]} │ {symbol}")
print("└───┘")
3.3. Demo Stack Operations¶
# Khởi tạo stack
stack = Stack()
print("=== PUSH Operations ===")
# Push các phần tử
stack.push(1)
stack.push(2)
stack.push(3)
stack.push(4)
print(f"\nStack size: {stack.size()}")
stack.display()
print("\n=== PEEK Operation ===")
print(f"Top element: {stack.peek()}")
print("\n=== POP Operations ===")
# Pop các phần tử
while not stack.is_empty():
popped = stack.pop()
print(f"Current stack size: {stack.size()}")
if not stack.is_empty():
stack.display()
else:
print("Stack is now empty")
Output:
=== PUSH Operations ===
Pushed 1 onto stack
Pushed 2 onto stack
Pushed 3 onto stack
Pushed 4 onto stack
Stack size: 4
Stack (top to bottom):
│ 4 │ ← TOP
│ 3 │
│ 2 │
│ 1 │
└───┘
=== PEEK Operation ===
Top element: 4
=== POP Operations ===
Popped 4 from stack
Current stack size: 3
Stack (top to bottom):
│ 3 │ ← TOP
│ 2 │
│ 1 │
└───┘
Popped 3 from stack
Current stack size: 2
Stack (top to bottom):
│ 2 │ ← TOP
│ 1 │
└───┘
Popped 2 from stack
Current stack size: 1
Stack (top to bottom):
│ 1 │ ← TOP
└───┘
Popped 1 from stack
Current stack size: 0
Stack is now empty
4. Nguyên Tắc LIFO (Last In, First Out)¶
4.1. Minh họa LIFO¶
def demonstrate_lifo():
"""Demo nguyên tắc LIFO của stack"""
stack = Stack()
# Thứ tự thêm vào: 1 → 2 → 3 → 4
elements_to_add = [1, 2, 3, 4]
print("Thứ tự THÊM VÀO:")
for elem in elements_to_add:
stack.push(elem)
print(f"\nStack sau khi thêm: {stack.items}")
print("\nThứ tự LẤY RA:")
removed_elements = []
while not stack.is_empty():
removed_elements.append(stack.pop())
print(f"Thứ tự thêm vào: {elements_to_add}")
print(f"Thứ tự lấy ra: {removed_elements}")
print("→ Thứ tự ngược nhau (LIFO)!")
demonstrate_lifo()
Output:
Thứ tự THÊM VÀO:
Pushed 1 onto stack
Pushed 2 onto stack
Pushed 3 onto stack
Pushed 4 onto stack
Stack sau khi thêm: [1, 2, 3, 4]
Thứ tự LẤY RA:
Popped 4 from stack
Popped 3 from stack
Popped 2 from stack
Popped 1 from stack
Thứ tự thêm vào: [1, 2, 3, 4]
Thứ tự lấy ra: [4, 3, 2, 1]
→ Thứ tự ngược nhau (LIFO)!
5. Ứng Dụng Thực Tế của Stack¶
5.1. Đảo Ngược Chuỗi/Mảng¶
def reverse_string_with_stack(s):
"""Đảo ngược chuỗi sử dụng stack"""
stack = Stack()
# Push từng ký tự vào stack
for char in s:
stack.push(char)
# Pop từng ký tự để tạo chuỗi đảo ngược
reversed_str = ""
while not stack.is_empty():
reversed_str += stack.pop()
return reversed_str
# Test
original = "HELLO"
reversed_str = reverse_string_with_stack(original)
print(f"Original: {original}")
print(f"Reversed: {reversed_str}")
5.2. Kiểm Tra Dấu Ngoặc Hợp Lệ (Balanced Parentheses)¶
def is_balanced_parentheses(expression):
"""Kiểm tra dấu ngoặc có cân bằng không"""
stack = Stack()
# Mapping các cặp ngoặc
pairs = {')': '(', '}': '{', ']': '['}
opening = {'(', '{', '['}
closing = {')', '}', ']'}
for char in expression:
if char in opening:
stack.push(char)
elif char in closing:
if stack.is_empty():
return False # Ngoặc đóng không có ngoặc mở tương ứng
if stack.pop() != pairs[char]:
return False # Ngoặc không khớp
return stack.is_empty() # Stack phải rỗng để cân bằng
# Test cases
test_cases = [
"()", # True
"(())", # True
"()[]{} ", # True
"([{}])", # True
"(((", # False
"))", # False
"([)]", # False
"{[}]" # False
]
for test in test_cases:
result = is_balanced_parentheses(test)
print(f"'{test}' → {result}")
5.3. Calculator Expression Evaluation (Tính toán biểu thức)¶
def evaluate_postfix(expression):
"""Tính toán biểu thức dạng postfix (Reverse Polish Notation)"""
stack = Stack()
operators = {'+', '-', '*', '/'}
tokens = expression.split()
for token in tokens:
if token not in operators:
# Là số, push vào stack
stack.push(int(token))
else:
# Là operator, pop 2 số và tính toán
if stack.size() < 2:
raise ValueError("Invalid expression")
b = stack.pop() # Số thứ 2
a = stack.pop() # Số thứ 1
if token == '+':
result = a + b
elif token == '-':
result = a - b
elif token == '*':
result = a * b
elif token == '/':
if b == 0:
raise ValueError("Division by zero")
result = a / b
stack.push(result)
if stack.size() != 1:
raise ValueError("Invalid expression")
return stack.pop()
# Test
postfix_expr = "3 4 + 2 * 7 /"
result = evaluate_postfix(postfix_expr)
print(f"Expression: {postfix_expr}")
print(f"Result: {result}")
# (3 + 4) * 2 / 7 = 14 / 7 = 2.0
5.4. Function Call Stack (Stack gọi hàm)¶
def function_call_demo():
"""Demo mô phỏng stack gọi hàm"""
call_stack = Stack()
def function_a():
call_stack.push("function_a() called")
print("Entering function_a")
call_stack.display()
function_b()
print("Exiting function_a")
call_stack.pop()
call_stack.display()
def function_b():
call_stack.push("function_b() called")
print("Entering function_b")
call_stack.display()
function_c()
print("Exiting function_b")
call_stack.pop()
call_stack.display()
def function_c():
call_stack.push("function_c() called")
print("Entering function_c")
call_stack.display()
print("Executing function_c")
print("Exiting function_c")
call_stack.pop()
call_stack.display()
function_a()
function_call_demo()
6. Ưu và Nhược Điểm của Stack¶
6.1. Ưu điểm¶
- Đơn giản: Dễ hiểu và triển khai
- Hiệu quả: Tất cả thao tác cơ bản đều O(1)
- Quản lý bộ nhớ: Tự động với dynamic array
- Linh hoạt: Có thể chứa bất kỳ kiểu dữ liệu nào
6.2. Nhược điểm¶
- Truy cập hạn chế: Chỉ có thể truy cập phần tử ở đỉnh
- Không thể duyệt: Không thể duyệt qua tất cả phần tử mà không pop
- Overhead: Dynamic array có thể tốn bộ nhớ khi mở rộng
7. So Sánh Stack với Các Cấu Trúc Dữ Liệu Khác¶
| Cấu trúc | Thêm | Xóa | Truy cập | Đặc điểm |
|---|---|---|---|---|
| Stack | O(1) - cuối | O(1) - cuối | O(1) - cuối | LIFO |
| Queue | O(1) - cuối | O(1) - đầu | O(1) - đầu/cuối | FIFO |
| Array | O(1) - cuối | O(1) - cuối | O(1) - bất kỳ | Random access |
| Linked List | O(1) - đầu | O(1) - đầu | O(n) - duyệt | Dynamic size |
8. Khi Nào Nên Sử Dụng Stack?¶
✅ Nên sử dụng Stack khi:¶
- Cần nguyên tắc LIFO (Last In, First Out)
- Cần "undo" operations (như Ctrl+Z)
- Xử lý biểu thức toán học (infix to postfix)
- Kiểm tra tính hợp lệ của dấu ngoặc
- Quản lý function calls
- Backtracking algorithms
- Depth-First Search (DFS)
❌ Không nên sử dụng Stack khi:¶
- Cần truy cập ngẫu nhiên vào các phần tử
- Cần duyệt qua tất cả phần tử
- Cần nguyên tắc FIFO (dùng Queue thay thế)
- Cần tìm kiếm trong dữ liệu (dùng Hash Map hoặc Tree)
10. Bài Tập Thực Hành¶
Bài 1: Valid Parentheses (LeetCode Easy)¶
Cho một chuỗi chỉ chứa các ký tự '(', ')', '{', '}', '[', ']', hãy xác định xem chuỗi có hợp lệ không.
Bài 2: Min Stack (LeetCode Medium)¶
Thiết kế một stack hỗ trợ push, pop, top và getMin trong thời gian O(1).
Bài 3: Evaluate Reverse Polish Notation (LeetCode Medium)¶
Tính toán giá trị của một biểu thức dạng Reverse Polish Notation.
11. Tổng Kết¶
Stack là một cấu trúc dữ liệu fundamental mà mọi developer cần nắm vững:
- Nguyên tắc LIFO là cốt lõi của Stack
- Triển khai đơn giản bằng dynamic array
- Hiệu suất cao với tất cả thao tác O(1)
- Ứng dụng rộng rãi từ parsing đến backtracking
- Nền tảng cho nhiều thuật toán và hệ thống phức tạp
Việc hiểu sâu về Stack không chỉ giúp bạn giải quyết các bài toán coding mà còn giúp hiểu rõ hơn về cách máy tính hoạt động và quản lý bộ nhớ.
Lời khuyên: Hãy thực hành triển khai Stack từ đầu và giải các bài tập related để thực sự master cấu trúc dữ liệu quan trọng này!