Ngăn xếp Python: Triển khai cấu trúc dữ liệu LIFO

Mỗi lần bạn nhấn Ctrl+Z để hoàn tác một lỗi, bấm nút quay lại trên trình duyệt, hoặc xem một hàm đệ quy “xả cuộn” kết quả, bạn đang dựa vào một ngăn xếp. Vì chúng ăn sâu trong phần mềm bạn dùng hằng ngày, bạn thường tương tác với ngăn xếp mà không hề nhận ra.

Trong bài viết này, chúng ta sẽ tìm hiểu ngăn xếp là gì, logic cốt lõi đằng sau ngăn xếp, so sánh các chiến lược triển khai sử dụng thư viện tích hợp của Python, và áp dụng chúng để giải các bài toán thuật toán.

Tôi khuyến nghị bạn học khóa học của chúng tôi về Viết mã Python hiệu quả để kết hợp kiến thức cấu trúc dữ liệu với các thực hành hiệu năng tốt, và luôn giữ Phiếu gợi ý Python cơ bản bên cạnh như một tài liệu tra cứu nhanh. 

Ngăn xếp trong Python là gì?

Trước khi xem code, điều quan trọng là hiểu nền tảng khái niệm khiến ngăn xếp Python trở thành một công cụ mạnh mẽ. Hãy xem nguyên lý cốt lõi đằng sau ngăn xếp và chúng khác gì so với các cấu trúc dữ liệu phổ biến khác.

Cấu trúc dữ liệu LIFO

Ngăn xếp là một cấu trúc dữ liệu tuyến tính tuân theo nguyên tắc Last-In-First-Out (LIFO). Nghĩa là phần tử được thêm gần đây nhất sẽ luôn là phần tử bị loại bỏ đầu tiên. Hãy tưởng tượng như một chồng đĩa trong căng-tin. Bạn đặt đĩa mới lên trên và luôn nhấc chiếc ở trên cùng trước. Bạn không bao giờ rút một chiếc từ giữa hay đáy. Truy cập hoàn toàn bị giới hạn ở đỉnh.

Chính ràng buộc duy nhất này — chỉ truy cập ở đỉnh — mang lại cho ngăn xếp tính dự đoán và hiệu quả. Mọi phần tử vào và ra cùng một đầu, giúp thao tác đơn giản và nhanh.

Một điểm đáng lưu ý sớm là Python không cung cấp một kiểu ngăn xếp nguyên thủy chuyên biệt như một số ngôn ngữ khác. Không có từ khóa stack hay lớp dựng sẵn. Thay vào đó, Python cung cấp các lựa chọn tích hợp mạnh mẽ như list, collections.deque và queue.LifoQueue — tất cả đều có thể hoạt động như ngăn xếp. Chúng ta sẽ xem chi tiết từng triển khai ở phần sau.

Ngăn xếp so với các cấu trúc dữ liệu khác

Hiểu ngăn xếp là gì sẽ rõ ràng hơn khi bạn thấy nó không phải là gì. Hai cấu trúc thường được so sánh với ngăn xếp là hàng đợi (queue) và list chuẩn của Python.

Ngăn xếp và hàng đợi

Hàng đợi tuân theo nguyên tắc First-In-First-Out (FIFO), đối nghịch với ngăn xếp. Trong hàng đợi, phần tử được thêm ở cuối và loại bỏ ở đầu, giống như một hàng người chờ mua vé. Ngăn xếp và hàng đợi đều tuyến tính và đều hạn chế cách bạn truy cập phần tử, nhưng theo hai hướng đối lập. 

Chọn nhầm có thể âm thầm phá vỡ logic của thuật toán. Ví dụ, thay thế ngăn xếp bằng hàng đợi trong duyệt theo chiều sâu (DFS) sẽ biến nó thành duyệt theo chiều rộng (BFS), tạo ra kết quả hoàn toàn khác.

Ngăn xếp và list

Ngược lại, một list Python chuẩn cung cấp truy cập ngẫu nhiên. Bạn có thể đọc, chèn, hoặc xóa phần tử tại bất kỳ chỉ số nào bằng các thao tác như my_list[3] hoặc my_list.insert(2, value). Tính linh hoạt này hữu ích trong nhiều ngữ cảnh, nhưng nó cũng có nghĩa là không có gì ngăn bạn vô tình truy cập hoặc sửa phần tử ở giữa cấu trúc. 

Khi bạn triển khai một thuật toán phụ thuộc chặt chẽ vào thứ tự LIFO, như quay lui (backtracking), phân tích cú pháp, hoặc chức năng hoàn tác, bản chất không giới hạn của list có thể đưa vào những lỗi tinh vi.

Đây chính là lý do mô hình truy cập hạn chế của ngăn xếp là một tính năng chứ không phải hạn chế. Bằng cách chỉ cho phép tương tác với phần tử trên cùng, ngăn xếp Python đảm bảo tính đúng đắn theo thiết kế. Bạn không thể vô tình lấy từ sai đầu hoặc ghi đè một phần tử nằm sâu bên trong cấu trúc. 

Trong thiết kế thuật toán, các ràng buộc như vậy giúp logic của bạn gọn gàng và code dễ dự đoán.

Các phép toán cốt lõi của ngăn xếp và độ phức tạp thời gian

Giờ chúng ta đã hiểu ngăn xếp Python là gì và nó khác gì so với các cấu trúc khác, hãy xem các phép toán cơ bản mà mọi ngăn xếp hỗ trợ và phân tích hiệu quả của từng phép.

Các phép toán tiêu chuẩn của ngăn xếp

Mọi triển khai ngăn xếp đều dựa trên một tập nhỏ các phép toán tiêu chuẩn, bất kể ngôn ngữ lập trình. Đây là các khối xây dựng bạn sẽ dùng mỗi khi làm việc với ngăn xếp.

Push thêm một phần tử vào đỉnh ngăn xếp. Nếu ngăn xếp chứa [A, B] và bạn push C, ngăn xếp thành [A, B, C], với C ở trên cùng.

Pop loại bỏ và trả về phần tử hiện tại ở đỉnh. Tiếp tục ví dụ trên, pop từ [A, B, C] trả về C và để lại ngăn xếp là [A, B].

Peek (đôi khi gọi là top) cho phép bạn xem phần tử ở đỉnh mà không loại bỏ nó. Điều này hữu ích khi logic của bạn cần kiểm tra giá trị đỉnh hiện tại trước khi quyết định có pop hay không — một mẫu thường gặp trong phân tích biểu thức và bài toán dấu ngoặc cân bằng.

Bên cạnh ba phép toán cốt lõi đó, hai phương thức trợ giúp quan trọng để viết code ngăn xếp an toàn, không lỗi:

• is_empty() kiểm tra ngăn xếp có phần tử nào không. Gọi pop hoặc peek trên ngăn xếp rỗng là nguồn lỗi runtime phổ biến, nên kiểm tra rỗng trước là thói quen lập trình phòng thủ bạn nên xây dựng sớm.

• size() trả về số phần tử hiện có trong ngăn xếp. Điều này hữu ích khi bạn cần theo dõi độ sâu đệ quy hoặc còn bao nhiêu mục cần xử lý.

Cuối cùng, đáng để định nghĩa một thuật ngữ bạn sẽ gặp trong giáo trình và phỏng vấn: Tràn ngăn xếp theo hướng âm (Stack Underflow). Đây là trạng thái lỗi xảy ra khi bạn cố gắng pop hoặc peek từ ngăn xếp rỗng. Không có gì để loại bỏ hay xem, nên thao tác không hợp lệ. 

Ngoại lệ hay hành vi chính xác sẽ phụ thuộc vào triển khai. Chúng ta sẽ thấy Python xử lý thế nào khi xem list, deque và LifoQueue ở phần tiếp theo.

Phân tích độ phức tạp

Một trong những lý do lớn khiến ngăn xếp được dùng rộng rãi trong thuật toán là hiệu quả của chúng. Hãy phân tích độ phức tạp thời gian và không gian của từng phép.

Push có độ phức tạp O(1). Trong một triển khai ngăn xếp hiệu quả, thêm một phần tử vào đỉnh là thao tác thời gian hằng số. Ngăn xếp không cần dịch chuyển hay sắp xếp lại phần tử hiện có. Nó chỉ đơn giản đặt mục mới vào cuối. Điều này đúng với cả collections.deque và, ở trường hợp trung bình (amortized), với list dựng sẵn của Python.

Pop là O(1). Loại bỏ phần tử đỉnh cũng nhanh tương tự. Ngăn xếp truy cập trực tiếp vị trí cuối, trả về giá trị và giảm bộ đếm kích thước nội bộ. Không cần dịch chuyển phần tử khác.

Peek là O(1). Xem phần tử đỉnh mà không loại bỏ là tra cứu chỉ số trực tiếp, cũng là thời gian hằng số.

Tìm kiếm là O(n). Đây là nơi ngăn xếp bộc lộ đánh đổi có chủ đích. Nếu bạn cần xác định một giá trị cụ thể có tồn tại đâu đó trong ngăn xếp hay không, bạn buộc phải quét qua toàn bộ n phần tử từ trên xuống dưới. 

Ngăn xếp không được thiết kế cho tra cứu tùy ý. Chúng hi sinh khả năng tìm kiếm để đổi lấy push và pop nhanh, có thể dự đoán. Nếu trường hợp sử dụng của bạn cần tìm kiếm thường xuyên, một cấu trúc khác như set hoặc dictionary sẽ phù hợp hơn.

Độ phức tạp không gian là O(n). Một ngăn xếp chứa n phần tử cần bộ nhớ tỷ lệ với n. Không có chi phí ẩn nào ngoài việc lưu chính các phần tử, cộng với một hằng số nhỏ cho sổ sách nội bộ của cấu trúc.

Tóm lược nhanh như sau:

Điểm mấu chốt là ngăn xếp Python được tối ưu để chèn và loại bỏ nhanh ở một đầu. Miễn là bạn dùng nó đúng mục đích — quản lý truy cập có thứ tự kiểu LIFO — nó cho hiệu năng rất tốt. Khi bạn thấy mình phải tìm kiếm thường xuyên trong một ngăn xếp, đó là tín hiệu nên xem xét lại lựa chọn cấu trúc dữ liệu.

Các triển khai ngăn xếp trong Python

Sau phần lý thuyết và phân tích độ phức tạp, giờ là lúc viết code thực sự. Python cung cấp ba cách chính để triển khai ngăn xếp, mỗi cách có điểm mạnh và đánh đổi riêng. Hãy đi qua cả ba và xem cách chọn lựa phù hợp cho trường hợp của chúng ta.

Ngăn xếp Python bằng list dựng sẵn

Cách đơn giản nhất để tạo ngăn xếp Python là dùng list dựng sẵn. Vì list là mảng động hỗ trợ thêm và loại bỏ phần tử ở cuối, chúng ánh xạ tự nhiên với hành vi ngăn xếp. 

Phương thức .append() đóng vai trò push, và .pop() không có đối số sẽ loại bỏ và trả về phần tử cuối. Hãy xem ví dụ dưới đây:

# Creating a stack using a Python list
stack = []

# Push elements
stack.append(10)
stack.append(20)
stack.append(30)
print(stack)

# Pop the top element
top = stack.pop()
print(top)
print(stack)

# Peek at the top element
print(stack[-1])

[10, 20, 30]
30
[10, 20]
20

Cách này hoạt động tốt, nhưng bạn cần xử lý cẩn thận trường hợp ngăn xếp rỗng. Trong Python, cả .pop() và stack[-1] sẽ ném IndexError khi list rỗng. Đây là cách Python biểu thị trạng thái Underflow mà ta đã định nghĩa trước đó. 

Thực hành tốt nhất là bọc các lời gọi này trong khối try/except hoặc kiểm tra rỗng trước khi truy cập đỉnh, như ví dụ sau:

# Handling Stack Underflow with try/except
stack = []

try:
    stack.pop()
except IndexError:
    print("Stack Underflow: cannot pop from an empty stack")

try:
    top = stack[-1]
except IndexError:
    print("Stack Underflow: cannot peek at an empty stack")

# Alternatively, check before accessing
if stack:
    top = stack.pop()
else:
    print("Stack is empty")

Stack Underflow: cannot pop from an empty stack
Stack Underflow: cannot peek at an empty stack
Stack is empty

Có một sắc thái hiệu năng đáng để hiểu. List Python được chống lưng bởi mảng động. Khi bạn gọi .append(), thao tác thường là O(1) tức thì. Tuy nhiên, khi mảng nội bộ hết vùng nhớ cấp sẵn, Python phải cấp phát một khối bộ nhớ lớn hơn và sao chép tất cả phần tử hiện có sang đó. 

Việc cấp phát lại không thường xuyên này khiến .append() có độ phức tạp O(1) theo trung bình cộng dồn (amortized) thay vì O(1) tuyệt đối. Trong thực tế, độ trễ này hiếm và ngắn, nhưng trong các ứng dụng nhạy cảm độ trễ hoặc thời gian thực, tính không thể đoán này có thể quan trọng.

Dù có lưu ý này, .append() và .pop() trên list vẫn là cách ưu tiên cho hầu hết tác vụ ngăn xếp đơn giản. Không cần import, cú pháp quen thuộc và mức độ quen dùng rộng rãi khiến nó là lựa chọn mặc định tốt, đặc biệt cho script, thử nghiệm nhanh, và bài phỏng vấn nơi sự đơn giản là quan trọng.

Ngăn xếp Python bằng collections.deque

Nếu bạn cần hiệu năng O(1) ổn định mà không có độ trễ cấp phát lại thỉnh thoảng, collections.deque là lựa chọn nâng cấp khuyến nghị. Tên gọi là "double-ended queue" (hàng đợi hai đầu), nhưng nó hoạt động hoàn hảo như một ngăn xếp Python hiệu năng cao. Ví dụ trước của chúng ta với cú pháp deque sẽ như sau:

from collections import deque

# Creating a stack using deque
stack = deque()

# Push elements
stack.append(10)
stack.append(20)
stack.append(30)
print(stack) 

# Pop the top element
top = stack.pop()
print(top)
print(stack)
 
# Peek at the top element
print(stack[-1])

deque([10, 20, 30])
30
deque([10, 20])
20

Lưu ý giao diện giống hệt cách dùng list. .append(), .pop() và [-1] đều hoạt động như nhau. Hành vi IndexError khi truy cập rỗng cũng không đổi, nên mã xử lý lỗi của bạn không cần chỉnh sửa:

from collections import deque

stack = deque()

try:
    stack.pop()
except IndexError:
    print("Stack Underflow: cannot pop from an empty deque stack")

Stack Underflow: cannot pop from an empty deque stack

Điểm khác biệt then chốt nằm ở bên trong. deque được triển khai như một danh sách liên kết đôi của các khối kích thước cố định thay vì một mảng đơn. Điều này có nghĩa nó không bao giờ cần cấp phát lại và sao chép toàn bộ cấu trúc khi tăng trưởng. 

Mỗi .append() và .pop() đều là O(1) thực sự, được đảm bảo — không phải amortized mà là nhất quán. Với công việc nặng thuật toán, nơi bạn push và pop hàng nghìn hay hàng triệu lần, tính nhất quán này cộng dồn đáng kể.

Ngăn xếp Python bằng queue.LifoQueue

Thư viện chuẩn của Python cũng bao gồm queue.LifoQueue, một triển khai ngăn xếp được thiết kế riêng cho chương trình đa luồng. "LIFO" trong tên xác nhận nó tuân theo thứ tự Last-In-First-Out, nhưng giao diện và hành vi khá khác so với hai cách trước. Hãy xem ví dụ sau:

from queue import LifoQueue

# Creating a thread-safe stack
stack = LifoQueue()

# Push elements using .put()
stack.put(10)
stack.put(20)
stack.put(30)
print(stack.qsize())

# Pop the top element using .get()
top = stack.get()
print(top)
print(stack.qsize())

3
30
2

Điều đầu tiên cần chú ý là thay đổi cú pháp. Push trở thành .put(), và pop trở thành .get(). Cách đặt tên này đến từ mẫu thiết kế producer-consumer của mô-đun queue, nơi một luồng "put" mục và luồng khác "get" chúng.

Có hai khác biệt hành vi quan trọng cần lưu ý. 

Thứ nhất, LifoQueue không có phương thức peek an toàn. Không có cách dựng sẵn để xem phần tử đỉnh mà không loại bỏ nó. Bạn có thể truy cập thuộc tính nội bộ, nhưng làm vậy trong bối cảnh đa luồng sẽ phản tác dụng mục đích dùng lớp an toàn luồng và có nguy cơ điều kiện tranh chấp.

Thứ hai, LifoQueue không ném IndexError khi bạn cố lấy từ ngăn xếp rỗng. Mặc định, .get() sẽ chặn. Nó tạm dừng luồng gọi và chờ vô hạn cho đến khi luồng khác put một mục vào ngăn xếp. Nếu bạn muốn hành vi không chặn, có thể truyền block=False, khi đó sẽ ném ngoại lệ queue.Empty. Hãy xem ví dụ:

from queue import LifoQueue, Empty

stack = LifoQueue()

# Non-blocking get raises Empty, not IndexError
try:
    stack.get(block=False)
except Empty:
    print("Stack is empty — no items to get")

Stack is empty — no items to get

Vì cơ chế khóa nội bộ giúp LifoQueue an toàn luồng, các thao tác của nó mang nhiều chi phí hơn so với list hay deque. Điều này khiến nó là lựa chọn kém phù hợp cho code đơn luồng. Chỉ dùng LifoQueue khi bạn có kịch bản đa luồng tự nhiên với truy cập đồng thời, còn lại hãy chọn deque hoặc list.

Chọn triển khai ngăn xếp phù hợp trong Python

Với ba lựa chọn, đây là so sánh cạnh nhau để định hướng quyết định của bạn:

Đây là khung ra quyết định của tôi để chọn triển khai phù hợp:

• Dùng list khi bạn cần một ngăn xếp nhanh không cần import, như trong script, notebook, và bảng trắng phỏng vấn. 

• Dùng collections.deque khi bạn viết code thuật toán, xử lý tập dữ liệu lớn, hoặc xây dựng bất cứ thứ gì mà hiệu năng quan trọng. 

• Chỉ dùng queue.LifoQueue khi bạn có kịch bản đa luồng tự nhiên với truy cập đồng thời.

Bạn cũng có thể bắt gặp các hướng dẫn tự triển khai ngăn xếp Python từ đầu bằng một lớp danh sách liên kết tùy chỉnh, nơi mỗi node giữ một giá trị và con trỏ tới node bên dưới. Theo tôi, đó chắc chắn là một bài tập học thuật giá trị giúp đào sâu hiểu biết về cách ngăn xếp hoạt động nội tại và cách tham chiếu bộ nhớ xâu chuỗi với nhau. 

Tuy nhiên, trong code Python sản xuất, ngăn xếp kiểu danh sách liên kết hầu như luôn chậm hơn deque do chi phí tạo từng đối tượng node. Với công việc Python thực tế, collections.deque mang lại sự kết hợp tốt nhất giữa tốc độ, rõ ràng và độ tin cậy.

Ứng dụng của ngăn xếp Python

Hiểu cách triển khai ngăn xếp Python mới chỉ là một nửa bức tranh. Giá trị thực sự của ngăn xếp trở nên rõ ràng khi bạn thấy chúng giải các bài toán sẽ phức tạp hơn nhiều nếu không có thứ tự LIFO. Hãy xem ba ứng dụng kinh điển thường xuyên xuất hiện trong phỏng vấn lập trình, hệ thống phần mềm và thiết kế thuật toán.

Kiểm tra dấu ngoặc cân bằng

Bài toán dấu ngoặc cân bằng là một trong những câu hỏi ngăn xếp được hỏi thường xuyên nhất trong phỏng vấn kỹ thuật. Cho một chuỗi chứa các dấu ngoặc như (), [], và {}, bạn cần xác định liệu mỗi dấu mở đều có dấu đóng tương ứng theo đúng thứ tự không.

Logic này ánh xạ hoàn hảo với ngăn xếp. Khi quét chuỗi từ trái sang phải, push mỗi dấu mở vào ngăn xếp. Khi gặp dấu đóng, pop phần tử trên cùng và kiểm tra có khớp không.

Nếu ngăn xếp rỗng khi bạn cố pop, hoặc dấu vừa pop không khớp, chuỗi là không cân bằng. Sau khi xử lý toàn bộ chuỗi, ngăn xếp phải rỗng. Bất kỳ dấu mở còn sót lại nghĩa là có thứ chưa được đóng. Hãy xem ví dụ:

from collections import deque

def is_balanced(expression):
    stack = deque()
    matching = {')': '(', ']': '[', '}': '{'}

    for char in expression:
        if char in '([{':
            stack.append(char)
        elif char in ')]}':
            if not stack:
                return False  # closing bracket with nothing to match
            if stack.pop() != matching[char]:
                return False  # mismatched pair
    
    return len(stack) == 0  # stack should be empty if balanced

# Test cases
print(is_balanced("([])")) 
print(is_balanced("{[()]}"))
print(is_balanced("([)]"))
print(is_balanced("(("))
print(is_balanced(""))

True
True
False
False
True

Hãy lần vết qua "{[()]}" từng bước để thấy ngăn xếp hoạt động:

Ngăn xếp rỗng ở cuối, nên biểu thức cân bằng.

Cùng một logic này vượt xa các bài phỏng vấn. Trình biên dịch và thông dịch dùng nó để xác thực cú pháp, đảm bảo mọi thẻ, dấu ngoặc hoặc dấu phân cách mở trong mã nguồn đều có đối tương ứng. 

Nếu bạn từng thấy thông báo SyntaxError: unexpected EOF trong Python, bạn đã thấy một dạng kiểm tra này. Trình kiểm tra HTML, bộ phân tích JSON, và thậm chí cả linter tệp cấu hình đều dựa vào các biến thể của cách tiếp cận dựa trên ngăn xếp này.

Triển khai duyệt theo chiều sâu (DFS)

Duyệt theo chiều sâu là một trong các thuật toán duyệt đồ thị nền tảng, và ngăn xếp là cấu trúc dữ liệu điều khiển nó. Ý tưởng đơn giản: bắt đầu tại một nút, khám phá xa nhất có thể dọc theo một nhánh trước khi quay lui để thử nhánh kế tiếp. Tính LIFO của ngăn xếp Python khiến hành vi “đi sâu trước” diễn ra tự nhiên.

Hầu hết các khóa nhập môn dạy DFS bằng đệ quy, nơi call stack ngầm quản lý thứ tự duyệt. Tuy nhiên, cách đệ quy có giới hạn thực tế: mặc định Python giới hạn 1.000 khung đệ quy. 

Với đồ thị lớn hoặc lồng sâu, điều này dẫn đến RecursionError. Phiên bản lặp, dùng ngăn xếp tường minh, tránh được vấn đề này và cho bạn toàn quyền kiểm soát quá trình duyệt.

Hãy xem ví dụ code. Ta sẽ thực hiện DFS trên đồ thị sau:

from collections import deque

def dfs_iterative(graph, start):
    visited = set()
    stack = deque()
    stack.append(start)
    traversal_order = []

    while stack:
        node = stack.pop()
        if node not in visited:
            visited.add(node)
            traversal_order.append(node)
            # Push neighbors onto the stack
            # Reverse to maintain left-to-right order after LIFO popping
            for neighbor in reversed(graph[node]):
                if neighbor not in visited:
                    stack.append(neighbor)
    
    return traversal_order

# Example graph represented as an adjacency list
graph = {
    'A': ['B', 'C'],
    'B': ['D', 'E'],
    'C': ['F'],
    'D': [],
    'E': ['F'],
    'F': []
}

print(dfs_iterative(graph, 'A'))

['A', 'B', 'D', 'E', 'F', 'C']

Hãy lần vết việc thực thi để thấy ngăn xếp chi phối quá trình duyệt như thế nào:

Lưu ý cách thứ tự LIFO buộc thuật toán khám phá trọn các nhánh A → B → D và A → B → E → F trước khi quay lại thăm C. Đây chính là điểm phân biệt DFS với BFS, vốn dùng hàng đợi và khám phá tất cả láng giềng ở độ sâu hiện tại trước khi đi sâu hơn. 

Mẫu DFS lặp này hoạt động cho cả cây, đồ thị có hướng và vô hướng. Nó cũng là nền tảng cho các thuật toán nâng cao như sắp xếp topo, phát hiện chu trình, và giải mê cung, đố.

Quản lý thao tác hoàn tác/làm lại

Nếu bạn từng dùng trình soạn thảo văn bản, ứng dụng vẽ, hay bảng tính, bạn đã dựa vào hoàn tác và làm lại mà không cần nghĩ cơ chế bên dưới. Cơ chế này tao nhã, và chạy trên đúng hai ngăn xếp.

Một ngăn xếp hoàn tác lưu mọi hành động hoặc trạng thái khi người dùng thay đổi. Khi người dùng kích hoạt hoàn tác, trạng thái hiện tại được pop khỏi ngăn xếp hoàn tác và push sang ngăn xếp làm lại.

Nếu người dùng sau đó kích hoạt làm lại, trạng thái được pop từ ngăn xếp làm lại và đẩy trở lại ngăn xếp hoàn tác. Nếu người dùng thực hiện một thay đổi hoàn toàn mới sau khi hoàn tác, ngăn xếp làm lại bị xóa. Bạn không thể làm lại thứ đã bị ghi đè bởi hành động mới. Hãy xem ví dụ:

from collections import deque

class TextEditor:
    def __init__(self):
        self.content = ""
        self.undo_stack = deque()
        self.redo_stack = deque()

    def type_text(self, text):
        """Record current state and apply new text."""
        self.undo_stack.append(self.content)
        self.content += text
        self.redo_stack.clear()  # new action invalidates redo history

    def undo(self):
        """Revert to the previous state."""
        if not self.undo_stack:
            print("Nothing to undo")
            return
        self.redo_stack.append(self.content)
        self.content = self.undo_stack.pop()

    def redo(self):
        """Re-apply the last undone action."""
        if not self.redo_stack:
            print("Nothing to redo")
            return
        self.undo_stack.append(self.content)
        self.content = self.redo_stack.pop()

    def show(self):
        print(f'Content: "{self.content}"')

# Demonstrate the undo/redo flow
editor = TextEditor()
editor.type_text("Hello")
editor.show()                

editor.type_text(" World")
editor.show()                

editor.type_text("!")
editor.show()              

editor.undo()
editor.show()           

editor.undo()
editor.show()           

editor.redo()
editor.show()

editor.type_text(" Python")
editor.show()         

editor.redo()  

Content: "Hello"
Content: "Hello World"
Content: "Hello World!"
Content: "Hello World"
Content: "Hello"
Content: "Hello World"
Content: "Hello World Python"
Nothing to redo

Luồng di chuyển trạng thái giữa hai ngăn xếp theo một mẫu rõ ràng:

Mẫu hai-ngăn-xếp này không chỉ giới hạn ở trình soạn thảo văn bản. Nó xuất hiện ở bất cứ đâu người dùng cần khả năng lùi và tiến qua một chuỗi thay đổi (thực ra là gần như mọi nơi):

• Phần mềm chỉnh sửa ảnh
• Hoàn tác giao dịch cơ sở dữ liệu
• Quản lý trạng thái trò chơi

Nguyên lý nền tảng luôn giống nhau. Một ngăn xếp Python theo dõi lịch sử, ngăn xếp còn lại theo dõi tương lai, và thứ tự LIFO đảm bảo bạn luôn quay về trạng thái gần nhất trước tiên.

Các khái niệm nâng cao về ngăn xếp Python

Ngăn xếp cũng đóng vai trò quan trọng phía sau mọi chương trình Python bạn chạy, và chúng cung cấp các kỹ thuật tối ưu hóa có thể giảm đáng kể độ phức tạp thời gian của một số bài toán. Hãy xem cả hai khía cạnh nâng cao này.

Hiểu call stack

Mỗi khi bạn gọi một hàm trong Python, có điều gì đó diễn ra ở hậu trường mà bạn không trực tiếp kiểm soát. Python đẩy (push) một khung mới lên một cấu trúc dữ liệu nội bộ gọi là call stack. Khung này giữ biến cục bộ của hàm, tham số, và con trỏ quay lại dòng code khởi tạo lời gọi. 

Khi hàm kết thúc thực thi, khung của nó bị pop khỏi call stack, và điều khiển được trả về cho nơi gọi.

Bạn thực sự có thể quan sát hành vi này bằng một ví dụ đơn giản:

def function_c():
    print("Inside function_c")
    # At this point, the call stack holds:
    # [main → function_a → function_b → function_c]  (top)

def function_b():
    print("Inside function_b")
    function_c()

def function_a():
    print("Inside function_a")
    function_b()

function_a()

Inside function_a
Inside function_b
Inside function_c

Khi function_c thực thi, call stack có bốn khung xếp chồng lên nhau. Khi mỗi hàm hoàn tất, khung của nó bị pop theo thứ tự LIFO. function_c kết thúc trước, rồi function_b, rồi function_a, và cuối cùng là phạm vi mô-đun chính.

Đây chính là cơ chế làm cho đệ quy hoạt động. Mỗi lời gọi đệ quy đẩy một khung mới với biến cục bộ riêng, và kết quả được tháo cuộn khi các khung bị pop. Hãy xem ví dụ:

def factorial(n):
    if n <= 1:
        return 1
    return n * factorial(n - 1)

print(factorial(5))

# Call stack at deepest point:
# factorial(1)  ← top (returns 1)
# factorial(2)  ← waiting for factorial(1)
# factorial(3)  ← waiting for factorial(2)
# factorial(4)  ← waiting for factorial(3)
# factorial(5)  ← waiting for factorial(4)

120

Vấn đề nảy sinh khi đệ quy quá sâu. Python đặt giới hạn đệ quy mặc định là 1.000 khung để tránh call stack tiêu thụ hết bộ nhớ. Nếu hàm đệ quy của bạn vượt quá giới hạn này, Python sẽ ném RecursionError. Hãy xem ví dụ:

def infinite_recursion(n):
    return infinite_recursion(n + 1)

try:
    infinite_recursion(0)
except RecursionError:
    print("RecursionError: maximum recursion depth exceeded")

RecursionError: maximum recursion depth exceeded

Bạn có thể kiểm tra và chỉnh giới hạn này bằng mô-đun sys, dù tăng nó cần thận trọng:

import sys

print(sys.getrecursionlimit())  
sys.setrecursionlimit(5000)     # Increase with caution

5000

Điểm phân biệt quan trọng cần nhớ là call stack là một cấu trúc cấp hệ thống do chính trình thông dịch Python quản lý. Bạn không thể trực tiếp push hay pop từ nó. Các ngăn xếp list, deque và LifoQueue mà ta xây trước đó là cấu trúc dữ liệu do người dùng định nghĩa, nằm trong bộ nhớ heap của chương trình. Chúng phục vụ mục đích khác nhau, nhưng đều tuân thủ nguyên lý LIFO.

Dùng ngăn xếp đơn điệu (monotonic stack)

Ngăn xếp đơn điệu là biến thể chuyên biệt trong đó các phần tử được duy trì theo thứ tự không giảm hoặc không tăng (đôi khi là tăng/giảm nghiêm ngặt, tùy bài toán). Mỗi khi bạn push phần tử mới, trước tiên bạn pop tất cả phần tử vi phạm ràng buộc thứ tự. Đây là chìa khóa để giải cả một lớp bài toán tối ưu trong thời gian tuyến tính.

Ví dụ kinh điển là bài toán Phần tử lớn hơn kế tiếp (Next Greater Element): Cho một mảng số nguyên, tìm phần tử đầu tiên lớn hơn ở bên phải của mỗi phần tử. Cách brute-force dùng vòng lặp lồng nhau chạy O(n²). Với mỗi phần tử, bạn quét mọi thứ bên phải. Ngăn xếp đơn điệu giải trong O(n).

Điểm mấu chốt là bạn duyệt mảng từ phải sang trái, duy trì một ngăn xếp giảm dần. Với mỗi phần tử, bạn pop mọi phần tử trong ngăn xếp nhỏ hơn hoặc bằng nó. Những giá trị đó không bao giờ có thể là “phần tử lớn hơn kế tiếp” cho bất kỳ phần tử nào về sau ở bên trái. 

Phần còn lại trên đỉnh ngăn xếp sau khi pop là đáp án cho phần tử hiện tại. Sau đó bạn push phần tử hiện tại vào ngăn xếp. Hãy xem ví dụ code. Lưu ý rằng -1 trong trường hợp này nghĩa là không có số lớn hơn ở bên phải số đó:

from collections import deque

def next_greater_element(nums):
    n = len(nums)
    result = [-1] * n  # default: no greater element found
    stack = deque()     # monotonic decreasing stack (stores values)

    # Traverse from right to left
    for i in range(n - 1, -1, -1):
        # Pop elements that are not greater than current
        while stack and stack[-1] <= nums[i]:
            stack.pop()
        
        # If stack is not empty, top is the next greater element
        if stack:
            result[i] = stack[-1]
        
        # Push current element onto the stack
        stack.append(nums[i])

    return result

nums = [4, 5, 2, 25, 7, 18]
print(next_greater_element(nums))

[5, 25, 25, -1, 18, -1]

Hãy lần vết việc thực thi để thấy thuộc tính đơn điệu được duy trì thế nào:

Lưu ý rằng mỗi phần tử được push lên ngăn xếp đúng một lần và bị pop nhiều nhất một lần trong toàn bộ quá trình duyệt. Đây là lý do tổng độ phức tạp thời gian là O(n) mặc dù có vòng lặp while bên trong. Tổng số thao tác push và pop qua tất cả vòng lặp không vượt quá 2n.

Như tôi đã đề cập, có nhiều bài toán tương tự mà mẫu ngăn xếp đơn điệu tăng tốc từ O(n²) xuống O(n), chẳng hạn:

• Bài toán khoảng giá cổ phiếu (stock span): Với giá mỗi ngày, tìm bao nhiêu ngày liên tiếp trước đó có giá thấp hơn hoặc bằng.
• Hình chữ nhật lớn nhất trong biểu đồ cột: Tìm diện tích hình chữ nhật tối đa vừa khít dưới biểu đồ (một bài phỏng vấn mức khó kinh điển).
• Nhiệt độ hàng ngày: Cho một mảng nhiệt độ theo ngày, tìm số ngày phải đợi để có ngày ấm hơn.
• Giữ nước mưa: Tính lượng nước mưa bị giữ giữa các cột có độ cao khác nhau.

Trong mỗi trường hợp, ý tưởng cốt lõi giống nhau: ràng buộc đơn điệu cho phép bạn loại bỏ những phần tử không còn ảnh hưởng đến kết quả tương lai, từ đó cắt giảm không gian tìm kiếm từ bậc hai xuống tuyến tính.

Kết luận

Ngăn xếp là một trong những cấu trúc dữ liệu đầu tiên mọi lập trình viên học và cũng là một trong những cấu trúc cuối cùng họ ngừng tìm ra cách dùng mới — điều trớ trêu là ngược với bản chất Last-In-First-Out của nó. 

Trong bài viết này, chúng ta đã thấy cách ràng buộc LIFO có thể hữu ích trong nhiều tình huống khác nhau, từ xác thực dấu ngoặc lồng nhau và điều khiển duyệt theo chiều sâu đến quản lý trạng thái hoàn tác/làm lại và tối ưu hóa bài toán mảng bằng ngăn xếp đơn điệu. 

Nếu rút ra một khuyến nghị, thì là: hãy dùng collections.deque làm triển khai ngăn xếp Python mặc định của bạn, trừ khi bạn có lý do cụ thể để không dùng.

Bước tiếp theo, tôi khuyên bạn học khóa học của chúng tôi về Cấu trúc dữ liệu và Thuật toán trong Python.