Câu chuyện về cái ngăn xếp, cách IDE nhắc thiếu dấu đóng ngoặc và hai nút undo – redo

Bạn vừa gấp đống áo bỏ vào ngăn xếp và nhận ra cái sơ mi ngày mai đi chơi với người yêu nằm dưới đáy và giờ phải lôi ngược lại từng cái áo để lấy nó ra.

Bạn đang gõ code và vô tình xóa dấu đóng ngoặc rồi bị IDE bôi đỏ và “nhắc khéo”.

Bạn edit cái poster suốt mấy giờ đồng hồ và khách hàng chọn duyệt bản đầu tiên sau khi bạn đã sửa hơn tám chục bước vì lỡ làm trên đúng một file và giờ phải spam kịch liệt nút Ctrl + Z.

Ba câu chuyện tưởng chừng không liên quan nhưng lại liên quan một cách không tưởng như thế nào?

Câu trả lời là cả ba đều “dan díu” đến stack, một cấu trúc dữ liệu nhỏ mà có võ – đồng thời sẽ là ngôi sao sáng trong bài viết này.

Stack và cái ngăn xếp

Hiểu đơn giản thì stack là một mảng động (dynamic array) với cơ chế khá là “dị” theo kiểu last in first out (LIFO – vô sau ra trước) như một cái ngăn xếp – bạn cứ bỏ đồ chồng chất từ dưới lên, và khi cần lấy món nào đó, phải bắt đầu lôi từng cái từ trên xuống.

Cơ chế hoạt động của stack

Cũng vì vậy, stack có các đặc điểm như:

  • Là một mảng động – kích thước mảng có thể thay đổi liên tục.
  • Phần tử mới được thêm vào cuối mảng
  • Khi truy cập phần tử, cần ném từng phần tử ra để có thể đến đúng vị trí.
  • Hai động từ phổ biến được sử dụng khi nói đến stack là push (đẩy vào) và pop (ném ra).
Trực quan về push và pop

Các ngôn ngữ lập trình hiện tại phần lớn đã đều hỗ trợ cấu trúc dữ liệu stack, hoặc thậm chí các đặc trưng của stack (empty, push, pop) còn được tính hợp thẳng vào kiểu dữ liệu mảng để tránh tạo thêm kiểu dữ liệu mới (như trong Javascript, Python).

Tuy nhiên, nếu bạn có hứng thú muốn xây dựng stack từ kiểu dữ liệu mảng có sẵn (hoặc bị deadline của thầy cô yêu cầu), hãy xem xét cài đặt một số phương thức đặc trưng như sau:

  • size(): lấy kích thước – số lượng phần tử hiện có trong stack.
  • empty(): kiểm tra stack hiện có đang rỗng hay không.
  • push(item): thêm một phần tử vào cuối stack.
  • pop(): lấy phần tử trên cùng và loại bỏ nó ra khỏi stack.
  • top(): lấy phần tử trên cùng và không bỏ nó ra khỏi stack.

Stack và cách IDE nhắc thiếu dấu đóng ngoặc

Quên đóng ngoặc bị IDE “chửi” ngay

Bạn có bao giờ thắc mắc IDE hoặc text editor luôn biết khi nào bạn quên đóng ngoặc một hàm, một block hoặc một phép toán? Cơ chế hoạt động của việc kiểm tra này có thể được phát biểu dưới dạng một bài toán rất phổ biến khi học về stack – Balanced Brackets – kiểm tra chuỗi đóng mở ngoặc hợp lệ:

  • Input: Một chuỗi chỉ gồm dấu đóng mở ngoặc, bao gồm các kí tự ‘(‘, ‘[‘, ‘{‘ và ‘)’, ‘]’, ‘}’.
  • Output: Kiểm tra chuỗi đã được đóng mở ngoặc hợp lệ hay không.
  • Ví dụ về số chuỗi hợp lệ như (), {(())} hay {[]}()(){[]}
  • Ví dụ về một số chuỗi không hợp lệ như ()), {{{}), ()(]

Chi tiết về bài toán, bạn có thể tham khảo tại một số trang lập trình như Hackerrank hoặc keyword Balanced Brackets.

Khi duyệt qua các kí tự trong chuỗi đến kí tự đóng ngoặc, ta cần kiểm tra tương xứng với dấu mở ngoặc gần nhất vừa duyệt qua, sau đó lặp lại việc kiểm tra các cặp đóng – mở ngoặc khác theo tuần tự last in – first out (LIFO).

LIFO trong kiểm tra đóng mở ngoặc

Chính vì đặc trưng này, stack có thể xem là phương án tối ưu để giải quyết bài toán:

  • Duyệt từng kí tự trong chuỗi đóng mở ngoặc
  • Khi gặp kí tự mở ngoặc ‘(‘, ‘[‘, ‘{‘, thêm kí tự đó vào stack.
  • Khi gặp kí tự đóng ngoặc, ngay lập tức kiểm tra nó phải là dành cho kí tử mở ngoặc vừa gặp gần đây nhất. Nếu không, có thể kết luận ngay chuỗi không hợp lệ, nếu có thì tiếp tục duyệt và pop kí tự mở ngoặc.
  • Sau khi duyệt hết chuỗi, nếu stack vẫn không rỗng, tức là số lượng dấu đóng ngoặc vẫn chưa đủ tương xứng với số lượng các dấu mở ngoặc, chuỗi vẫn không hợp lệ. Và ngược lại, nếu stack rỗng – số lượng đóng mở ngoặc đã cân bằng và chuỗi được xem là hợp lệ.

Tư tưởng giải thuật có thể được tiếp cận như sau:

def isBalanceBrackets(brackets):
    1. define stack to hold open brackets
    2. for char in brackets:
          if char is open-bracket:
              push char to stack
          else if stack is empty:
              return false
          else:
              pop latest open-bracket in stack
              if open-bracket not match char:
                  return false
    3. return stack is empty

Bài toán Balanced Bracket khá phổ biến khi phỏng vấn về giải thuật tại một số công ty, hoặc có một số biến thể nâng cấp như sửa lỗi bằng cách thêm dấu đóng hoặc mở ngoặc để chuỗi hợp lệ; hoặc kiểm tra đóng mở ngoặc như IDE – chuỗi sẽ chứa thêm các kí tự khác và bạn cần xác định thêm dấu đóng mở ngoặc tại vị trí nào phù hợp.

Ngoài ra, bạn có thể tham khảo demo của mình tại đây.

Stack và hai nút undo – redo

Để giảm độ bi kịch của kịch bản sửa tám chục lần poster ban đầu, mình sẽ tiếp cận nút undo và redo theo bài toán đơn giản hơn – thuở hồng hoang khi chúng ta còn xài huyền thoại Paint để vẽ.

Bạn hì hục vẽ bãi biển đầy cát vàng và giờ phân vân tô màu biển là xanh da trời thăm thẳm, xanh lá ngọc ngà hay nâu nâu phù sa, bạn cứ tô màu mới rồi undo để xem màu cũ, rồi lại redo quay lại màu mới; rồi sau cùng chốt biển màu cam hoàng hôn chiều tím đầy mộng mơ không liên quan chẳng hạn.

Một kiệt tác của mình khi chọn màu cho bãi biển

Khi bạn nhấn Ctrl+Z (undo): màu mới bị ném ra vào một nơi khác, màu hiện tại sẽ là cái gần nhất mà bạn vừa thay đổi, nhấn bao nhiêu lần thì bị vứt bấy nhiêu đến khi không nhấn được nữa – là khi tác phẩm quay trở về là một tờ giấy trắng tinh khôi.

Khi bạn nhấn Ctrl+Y (redo): màu mà bạn đã ném ở bước undo sẽ được trả về, ví dụ bạn vừa undo nâu để có màu xanh lá -> tiếp tục undo để có màu xanh dương -> khi redo lần 1, màu xanh lá sẽ xuất hiện trước -> khi redo lần 2 sẽ là màu nâu xuất hiện.

Undo – redo màu bãi biển

Lắt léo hơn, khi bạn undo giữa chừng rồi chọn màu mới: bạn sẽ không thể redo được nữa. Cụ thể là khi bạn đang phân vân giữa xanh lá, xanh dương và nâu và đang đổi xoành xoạch rồi cuối cùng chốt là màu cam hoàng hôn, nút redo sẽ bị mất tác dụng ngay (dĩ nhiên bạn vẫn có thể undo nhé, sau đó lại dùng redo như thường).

Undo giữa chừng và chọn màu mới

Đến đây, bạn đã thấy vài đặc điểm của stack rồi đúng không? Ta sẽ sử dụng 2 stack để thực hiện màn “tung hứng” giữa undo và redo như trên.

Tư tưởng giải thuật có thể được tiếp cận như sau:

define stack for undo
define stack for redo
def set_color(new_color):
    1. if color is not changed:
        do nothing
    2. push current color to undo stack
    3. clear the redo-stack
    4. set new color to the beach
def undo():
    1. if undo stack is empty or color not changed:
        do nothing
    2. push current color to redo-stack
    3. pop undo-stack to get the old color
    4. set old color to the beach
def redo():
    1. if redo-stack is empty or color not changed:
        do nothing
    2. push current color to undo-stack
    3. pop redo-stack to get the new color
    4. set new color to the beach

Có thể dễ thấy, vì số lượng dữ liệu phải lưu ngày càng tăng, nên các ứng dụng thực tế thường quy định số lần undo-redo trong khoản giới hạn (có thể là một, một vài, vài chục, vài trăm hoặc vài ngàn bước…) để tránh tình trạng lưu trữ các trạng thái (state) quá nhiều dẫn đến tràn bộ nhớ (stackoverflow).

Bạn có thể tham khảo demo của mình tại đây.

Vài trò khác stack có thể làm

Ngoài hai trò kiểm tra đóng mở ngoặc và undo-redo, ứng dụng hoặc tư tưởng của stack cũng được sử dụng ở nhiều nơi như:

  • Cơ chế return trong đệ quy (hàm gọi sau sẽ được lấy giá trị trước).
  • Đảo ngược mảng/chuỗi.
  • Một số thuật toán trong lí thuyết đồ thị như DFS (Deep First Search).

Ngoài ra, nếu gặp bài toán có thể phát biểu theo đặc trưng last in – first out, hãy thử cân nhắc sử dụng stack để giải quyết nhé =)

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s