Khái niệm cơ bản về Ngăn xếp (Stack)

Ngăn xếp (Stack) là một dạng cấu trúc dữ liệu tuyến tính, nơi mà các thao tác thêm mới hoặc xóa bỏ phần tử chỉ được phép thực hiện tại một đầu duy nhất. Đầu này được gọi là đỉnh ngăn xếp (Top), trong khi đầu đối diện được xem là đáy (Bottom).

Thao tác đưa phần tử vào ngăn xếp được gọi là đẩy (Push), còn thao tác lấy phần tử ra được gọi là弹出 (Pop). Đặc trưng nổi bật nhất của cấu trúc này là nguyên tắc "Vào sau, ra trước" (Last In First Out - LIFO). Điều này có nghĩa là phần tử được đưa vào cuối cùng sẽ là phần tử được lấy ra đầu tiên, và ngược lại, phần tử vào đầu tiên sẽ nằm lại dưới đáy cho đến khi các phần tử phía trên được xử lý hết.

Ngăn xếp đóng vai trò quan trọng trong nhiều tình huống thực tế của lập trình như quản lý gọi hàm (function call), tính toán biểu thức toán học, hoặc kiểm tra sự cân bằng của các ký tự ngoặc.

Về mặt cài đặt, ngăn xếp có thể được xây dựng dựa trên mảng (Array) hoặc danh sách liên kết (Linked List). Khi dùng mảng, ta gọi là ngăn xếp tuần tự (Sequential Stack), còn khi dùng danh sách liên kết thì gọi là ngăn xếp liên kết (Linked Stack).

• Ngăn xếp tuần tự: Sử dụng một mảng cố định hoặc động cùng một biến chỉ mục để theo dõi vị trí đỉnh. Khi đẩy dữ liệu, chỉ mục tăng lên; khi lấy dữ liệu, chỉ mục giảm xuống.
• Ngăn xếp liên kết: Sử dụng các node liên kết. Đỉnh ngăn xếp thường trỏ vào node đầu tiên của danh sách. Việc đẩy dữ liệu tương đương với việc chèn node mới vào đầu danh sách, và lấy dữ liệu là xóa node đầu tiên.

Lưu ý về bộ nhớ: Cần phân biệt giữa Stack (Ngăn xếp) và Heap (Vùng nhớ động). Stack thường được hệ thống tự động quản lý việc cấp phát và giải phóng bộ nhớ (ví dụ: biến cục bộ), trong khi Heap đòi hỏi lập trình viên phải tự quản lý hoặc chờ hệ điều hành thu hồi khi chương trình kết thúc.

Cài đặt Ngăn xếp trong Python

Dưới đây là một ví dụ về cách xây dựng lớp ngăn xếp sử dụng danh sách động của Python. Cấu trúc này được tối ưu để hỗ trợ các thao tác cơ bản với độ phức tạp thời gian O(1).

class StackContainer:
    def __init__(self):
        # Khởi tạo vùng lưu trữ dữ liệu
        self._storage = []
    
    def push(self, element):
        """Đẩy một phần tử vào đỉnh ngăn xếp"""
        self._storage.append(element)

    def pop(self):
        """Lấy và xóa phần tử ở đỉnh ngăn xếp"""
        if not self.is_empty():
            return self._storage.pop()
        return None

    def peek(self):
        """Xem phần tử đỉnh mà không xóa"""
        if not self.is_empty():
            return self._storage[-1]
        return None

    def is_empty(self):
        """Kiểm tra xem ngăn xếp có rỗng không"""
        return len(self._storage) == 0

    def count(self):
        """Trả về số lượng phần tử hiện có"""
        return len(self._storage)

if __name__ == "__main__":
    stack = StackContainer()
    test_string = "({[({{abc}})][{1}]})2([]){({[]})}[]"
    pair_map = {')': '(', ']': '[', '}': '{'}
    
    for char in test_string:
        if char in '([{':
            stack.push(char)
        elif char in pair_map:
            top_element = stack.pop()
            if top_element != pair_map[char]:
                print("Kết quả: Không khớp")
                break
    else:
        if stack.is_empty():
            print("Kết quả: Khớp chính xác")
        else:
            print("Kết quả: Không khớp")

Các ứng dụng điển hình của Stack

1. Kiểm tra cân bằng ngoặc (Bracket Matching)

Bài toán kiểm tra ngoặc đóng mở có đúng cặp hay không là một ví dụ kinh điển cho thấy sức mạnh của ngăn xếp. Quy trình xử lý như sau: khi gặp ngoặc mở, ta đẩy vào stack; khi gặp ngoặc đóng, ta lấy phần tử đỉnh stack ra để đối chiếu. Nếu stack rỗng khi cần lấy hoặc ký tự lấy ra không tương ứng với ký tự đóng hiện tại, chuỗi đó không hợp lệ.

def validate_brackets(input_str):
    buffer = StackContainer()
    opening = set("([{")
    matching = {')': '(', ']': '[', '}': '{'}
    
    for symbol in input_str:
        if symbol in opening:
            buffer.push(symbol)
        elif symbol in matching:
            if buffer.is_empty():
                return False
            top_val = buffer.pop()
            if top_val != matching[symbol]:
                return False
                
    return buffer.is_empty()

# Kiểm thử các trường hợp
print(validate_brackets("()"))           # True
print(validate_brackets("()[]{}"))       # True
print(validate_brackets("(]"))           # False
print(validate_brackets("([)]"))         # False
print(validate_brackets("{[]}"))         # True

Trong đoạn mã trên, hàm validate_brackets sẽ duyệt qua từng ký tự. Nếu là ngoặc mở, nó được lưu trữ tạm thời. Nếu là ngoặc đóng, hệ thống kiểm tra tính tương thích với ngoặc mở gần nhất chưa được đóng. Cuối cùng, ngăn xếp phải trống thì biểu thức mới được coi là hợp lệ.

2. Tính toán biểu thức toán học

Ngăn xếp cũng thường được sử dụng để tính giá trị của các biểu thức số học. Một phương pháp phổ biến là sử dụng ký pháp nghịch đảo Ba Lan (Postfix Notation), nơi mà toán tử đứng sau toán hạng. Quá trình thực hiện là đẩy các số vào stack, khi gặp toán tử thì lấy hai số gần nhất ra để tính toán, sau đó đẩy kết quả ngược lại vào stack.

def calculate_postfix(expression):
    calc_stack = StackContainer()
    operators = {
        '+': lambda x, y: x + y,
        '-': lambda x, y: x - y,
        '*': lambda x, y: x * y,
        '/': lambda x, y: x / y
    }
    
    # Biểu thức đầu vào cần cách nhau bởi khoảng trắng để dễ xử lý
    tokens = expression.split()
    
    for token in tokens:
        if token.isdigit():
            calc_stack.push(int(token))
        elif token in operators:
            if calc_stack.count() < 2:
                raise ValueError("Biểu thức không hợp lệ")
            val2 = calc_stack.pop()
            val1 = calc_stack.pop()
            res = operators[token](val1, val2)
            calc_stack.push(res)
        else:
            raise ValueError(f"Toán tử không xác định: {token}")
            
    return calc_stack.pop()

# Ví dụ sử dụng ký pháp hậu tố (Postfix)
# "3 4 5 * +" tương đương 3 + (4 * 5) = 23
print(calculate_postfix("3 4 5 * +")) 
# "3 4 * 5 +" tương đương (3 * 4) + 5 = 17
print(calculate_postfix("3 4 * 5 +")) 
# "4 2 - 3 +" tương đương (4 - 2) + 3 = 5
print(calculate_postfix("4 2 - 3 +")) 
# "5 2 /" tương đương 5 / 2 = 2.5
print(calculate_postfix("5 2 /"))

Đoạn code trên định nghĩa một hàm calculate_postfix nhận vào chuỗi biểu thức dạng hậu tố. Nó sử dụng một từ điển operators để lưu trữ các hàm tính toán tương ứng, giúp mã nguồn gọn gàng và dễ mở rộng. Lưu ý rằng các toán hạng và toán tử trong chuỗi đầu vào cần được phân tách bằng khoảng trắng để bộ phân tích cú pháp hoạt động chính xác.