Cấu trúc dữ liệu và Giải thuật Bài 33: Ngăn xếp (Stack): Nguyên lý LIFO và thao tác cơ bản.

Mảng và Danh sách liên kết cung cấp cho bạn sự tự do tuyệt đối: Bạn có thể thêm, sửa, xóa dữ liệu ở đầu, giữa, hay cuối tùy thích. Tuy nhiên, trong kiến trúc hệ thống, sự tự do đôi khi lại là nguồn cơn của sự hỗn loạn. Bằng cách "khóa" các lối truy cập và ép dữ liệu phải tuân theo một kỷ luật di chuyển khắt khe, chúng ta tạo ra được những cỗ máy xử lý luồng logic cực kỳ mạnh mẽ.

Cấu trúc dữ liệu đầu tiên đại diện cho triết lý "kỷ luật thép" này chính là Ngăn xếp (Stack).

1. Nguyên lý LIFO (Last-In-First-Out)

Stack hoạt động dựa trên một nguyên lý duy nhất: LIFO - Vào sau, Ra trước.

Hãy tưởng tượng một chồng đĩa trong bữa tiệc Buffet. Khi nhân viên dọn thêm một chiếc đĩa sạch, họ đặt nó lên đỉnh của chồng đĩa. Khi một thực khách cần lấy đĩa, họ cũng phải lấy chiếc đĩa nằm trên đỉnh đó trước tiên. Chiếc đĩa đầu tiên được đặt xuống dưới cùng sẽ là chiếc đĩa cuối cùng được lấy ra.

Trong Stack, điểm truy cập duy nhất này được gọi là Top (Đỉnh). Bạn hoàn toàn mù tịt về những dữ liệu nằm bên dưới; bạn không thể rút một phần tử ở giữa ra mà không lấy tất cả các phần tử nằm trên nó ra trước.

2. Các thao tác cốt lõi (Core Operations)

Một Stack chuẩn mực chỉ phơi bày ra bên ngoài 4 thao tác API cơ bản. Sự tinh gọn này giúp nó đạt tốc độ vật lý tối đa $O(1)$ cho mọi thao tác.

1. Push (Đẩy vào): Thêm một phần tử mới lên Đỉnh (Top) của ngăn xếp.

2. Pop (Lấy ra): Lấy phần tử đang nằm trên Đỉnh ra khỏi ngăn xếp và trả về giá trị của nó. Nếu Stack đang rỗng mà bạn vẫn cố Pop, hệ thống sẽ ném ra lỗi Stack Underflow.

3. Peek / Top (Nhìn trộm): Đọc giá trị của phần tử trên Đỉnh mà không lấy nó ra.

4. IsEmpty (Kiểm tra rỗng): Trả về true nếu Stack không chứa phần tử nào. Đây là chốt chặn an toàn bắt buộc phải gọi trước khi thực hiện Pop.

3. Bản chất vật lý: Stack là một ADT (Abstract Data Type)

Khác với Mảng (phải cấp phát RAM liên tục) hay Linked List (cấp phát RAM rời rạc), Stack không quy định cách bộ nhớ vật lý được tổ chức bên dưới. Stack là một Kiểu dữ liệu trừu tượng (ADT) – nó chỉ là một bộ quy tắc logic.

Bạn hoàn toàn có thể xây dựng (implement) một Stack bằng Mảng, hoặc bằng Danh sách liên kết.

• Nếu dùng Linked List: Bạn luôn chèn Node mới vào vị trí Head (Push) và xóa Node tại vị trí Head (Pop).

• Nếu dùng Mảng (Dynamic Array/Slice): Bạn luôn append vào cuối mảng (Push) và xóa phần tử ở index = len - 1 (Pop).

Trong thực tế lập trình backend với Golang, việc dùng Slice để làm Stack phổ biến hơn nhờ tận dụng được hiệu năng tuyệt vời của CPU Cache (dữ liệu nằm liên tục) và Code cực kỳ ngắn gọn.

4. Triển khai Stack bằng Golang (Sử dụng Slice)

Go

type Stack struct {
    items []int
}

// Push tốn O(1) Amortized (Khấu hao)
func (s *Stack) Push(data int) {
    s.items = append(s.items, data)
}

// Pop tốn O(1)
func (s *Stack) Pop() (int, bool) {
    if s.IsEmpty() {
        return 0, false // Chống lỗi Stack Underflow
    }
    
    // Lấy chỉ số của phần tử trên cùng
    topIndex := len(s.items) - 1
    
    // Lưu lại giá trị để trả về
    poppedValue := s.items[topIndex]
    
    // Cắt bỏ phần tử trên cùng ra khỏi slice
    s.items = s.items[:topIndex]
    
    return poppedValue, true
}

// Peek tốn O(1)
func (s *Stack) Peek() (int, bool) {
    if s.IsEmpty() {
        return 0, false
    }
    return s.items[len(s.items)-1], true
}

func (s *Stack) IsEmpty() bool {
    return len(s.items) == 0
}

5. Ứng dụng định hình ngành Khoa học Máy tính

Sự xuất hiện của Stack không chỉ để giải bài tập, nó là xương sống của mọi hệ điều hành và trình biên dịch (Compiler):

• Call Stack (Ngăn xếp thực thi): Khi Hàm A gọi Hàm B, hệ điều hành phải tạm dừng Hàm A. Nó đóng gói toàn bộ biến cục bộ và trạng thái của Hàm A thành một Stack Frame và Push vào vùng nhớ Call Stack của RAM. Sau đó nó chạy Hàm B. Khi B chạy xong (return), hệ thống sẽ Pop Stack Frame của A ra để A tiếp tục chạy từ đúng dòng code bị tạm dừng. Nếu Hàm B gọi chính nó liên tục không có điểm dừng (Đệ quy vô hạn), bộ nhớ Stack sẽ bị đầy, gây ra lỗi StackOverflow kinh điển.

• Cơ chế Undo / Redo: Trong trình soạn thảo văn bản hoặc các phần mềm thiết kế đồ họa, mỗi thao tác gõ phím hoặc vẽ được Push vào một Stack (Lịch sử). Khi bạn bấm Ctrl + Z (Undo), hệ thống Pop hành động cuối cùng ra để khôi phục trạng thái trước đó.

• Điều hướng Browser (Nút Back / Forward): Lịch sử duyệt web của bạn được lưu trong một Stack. Trang hiện tại luôn là đỉnh của Stack. Khi bấm "Back", URL hiện tại bị Pop ra, đưa bạn về URL nằm ngay bên dưới.

Kỷ luật LIFO của Stack biến nó thành vũ khí tối thượng để giải quyết các bài toán có tính chất "lồng ghép" (nested) hoặc "đóng/mở". Ở bài học tiếp theo, chúng ta sẽ dùng Stack để bẻ khóa một câu hỏi phỏng vấn thường xuyên xuất hiện nhất trong lịch sử LeetCode: Kiểm tra tính hợp lệ của chuỗi dấu ngoặc.