Trong khoa học máy tính, cấu trúc dữ liệu stack (ngăn xếp) đóng vai trò là nền tảng cốt lõi cho việc quản lý bộ nhớ và điều hướng thuật toán. Hiểu rõ Stack không chỉ giúp bạn tối ưu code mà còn là chìa khóa để giải quyết các bài toán phức tạp như xử lý đệ quy hay biên dịch ngôn ngữ.
Hình ảnh mô phỏng cơ chế hoạt động LIFO của ngăn xếp thông qua các thao tác cơ bản Push và Pop
Bản chất và cơ chế vận hành của ngăn xếp
Về mặt logic, cấu trúc dữ liệu stack là một danh sách tuyến tính đặc biệt tuân thủ chặt chẽ nguyên lý LIFO (Last In, First Out – Vào sau, Ra trước). Điều này có nghĩa là phần tử cuối cùng được thêm vào danh sách sẽ là phần tử đầu tiên bị loại bỏ. Hãy tưởng tượng một chồng đĩa trong nhà hàng: bạn đặt đĩa mới lên trên cùng và khi cần sử dụng, bạn cũng lấy chiếc đĩa ở trên cùng đó ra trước.
Trong lập trình, ngăn xếp giới hạn quyền truy cập tại một vị trí duy nhất gọi là “đỉnh” (Top). Mọi thao tác bổ sung hay xóa bỏ đều phải thông qua điểm này. Chính sự ràng buộc này tạo nên tính hiệu quả cho các bài toán yêu cầu quay lui hoặc quản lý trạng thái tạm thời.
Phân tích các thao tác cơ bản trên ngăn xếp
Một cấu trúc dữ liệu stack tiêu chuẩn phải cung cấp tối thiểu bốn thao tác với độ phức tạp thời gian cố định O(1):
- đẩy vào (push): Thêm một phần tử mới vào đỉnh của ngăn xếp. Trong kịch bản thực tế, chúng ta cần kiểm tra điều kiện tràn (stack overflow) nếu sử dụng mảng tĩnh.
- lấy ra (pop): Loại bỏ phần tử ở đỉnh ngăn xếp và trả về giá trị của nó. Nếu ngăn xếp rỗng, thao tác này sẽ dẫn đến lỗi “stack underflow”.
- Xem đỉnh (peek/top): Trả về giá trị của phần tử ở đỉnh mà không xóa nó khỏi ngăn xếp. Hữu ích khi cần kiểm tra điều kiện trước khi xử lý logic.
- Kiểm tra rỗng (isEmpty): Xác định liệu ngăn xếp có chứa phần tử nào hay không, đây là bước kiểm tra an toàn (guard clause) bắt buộc trong mọi implement thực tế.
Hướng dẫn triển khai cấu trúc dữ liệu stack bằng Java 17
Có hai cách chính để cài đặt ngăn xếp: sử dụng mảng (Array) hoặc danh sách liên kết (Linked List). Trong hướng dẫn này, tôi sẽ trình bày cách dùng danh sách liên kết để đảm bảo tính linh hoạt về bộ nhớ, tránh giới hạn kích thước cố định.
// Ngôn ngữ: Java 17+
// Mục đích: Triển khai Generic Stack tối ưu hiệu năng bộ nhớ
public class GenericStack<T> {
// Lớp nội bộ để đại diện cho một nút trong danh sách liên kết
private static class Node<T> {
private T data;
private Node<T> next;
public Node(T data) {
this.data = data;
}
}
private Node<T> top; // Con trỏ quản lý đỉnh ngăn xếp
private int size; // Quản lý số lượng phần tử hiện tại
public GenericStack() {
this.top = null;
this.size = 0;
}
/
Thêm một phần tử vào cấu trúc dữ liệu stack
Time Complexity: O(1)
/
public void push(T value) {
if (value == null) {
throw new IllegalArgumentException("Giá trị không được null");
}
Node<T> newNode = new Node<>(value);
newNode.next = top; // Liên kết nút mới với đỉnh cũ
top = newNode; // Cập nhật đỉnh mới
size++;
}
/
Loại bỏ và trả về phần tử ở đỉnh
Time Complexity: O(1)
/
public T pop() {
if (isEmpty()) {
throw new java.util.EmptyStackException();
}
T data = top.data;
top = top.next; // Di chuyển con trỏ đỉnh xuống nút bên dưới
size--;
return data;
}
/
Truy xuất giá trị ở đỉnh mà không xóa
/
public T peek() {
if (isEmpty()) {
throw new java.util.EmptyStackException();
}
return top.data;
}
public boolean isEmpty() {
return top == null;
}
public int getSize() {
return size;
}
public static void main(String[] args) {
GenericStack<Integer> stack = new GenericStack<>();
// Test thao tác Push
stack.push(10);
stack.push(20);
stack.push(30);
System.out.println("Đỉnh hiện tại: " + stack.peek()); // Output: 30
// Test thao tác Pop
System.out.println("Lấy ra: " + stack.pop()); // Output: 30
System.out.println("Kích thước sau khi pop: " + stack.getSize()); // Output: 2
}
}So sánh triển khai: Mảng vs Danh sách liên kết
Khi thiết kế cấu trúc dữ liệu stack, việc chọn lựa cấu trúc nền tảng (underlying structure) ảnh hưởng trực tiếp đến hiệu năng hệ thống:
- Dựa trên Mảng (Array-based):
- Ưu điểm: Truy cập bộ nhớ tuần tự giúp CPU cache tốt hơn (locality of reference), không tốn thêm bộ nhớ cho các con trỏ
next. - Nhược điểm: Kích thước cố định. Khi mảng đầy, thao tác đẩy vào (push) tốn O(n) để cấp phát lại mảng mới và copy dữ liệu.
- Ưu điểm: Truy cập bộ nhớ tuần tự giúp CPU cache tốt hơn (locality of reference), không tốn thêm bộ nhớ cho các con trỏ
- Dựa trên Danh sách liên kết (Linked List-based):
- Ưu điểm: Cực kỳ linh hoạt, mở rộng động theo nhu cầu thực tế, thao tác thêm/xóa luôn ổn định ở O(1).
- Nhược điểm: Mỗi phần tử tốn thêm bộ nhớ cho con trỏ, có thể gây phân mảnh bộ nhớ nếu số lượng phần tử quá lớn.
| Tiêu chí | Ngăn xếp mảng | Ngăn xếp danh sách liên kết |
|---|---|---|
| đẩy vào (push) | O(1) trung bình | O(1) tuyệt đối |
| lấy ra (pop) | O(1) | O(1) |
| Bộ nhớ bổ sung | Thấp | Cao (do con trỏ) |
| Giới hạn | Có (Static Array) | Không |
Tại sao cấu trúc dữ liệu stack quan trọng trong thực tế?
Nếu bạn từng thắc mắc tại sao một chương trình bị crash kèm lỗi StackOverflowError, đó chính là hệ quả của việc sử dụng cấu trúc dữ liệu stack trong quản lý bộ nhớ (Execution Stack).
Trong hệ điều hành, mỗi tiến trình thường có hai vùng nhớ chính: Stack và Heap. Vùng Stack được dùng để lưu trữ các biến cục bộ và địa chỉ trả về của hàm. Khi hàm A gọi hàm B, một “Stack Frame” mới được đẩy vào (push). Khi hàm B thực thi xong, Frame đó được lấy ra (pop) để trả quyền điều khiển về hàm A. Nếu bạn dùng đệ quy vô hạn, vùng nhớ này sẽ đầy, gây ra lỗi hệ thống nghiêm trọng.
Hướng tới ứng dụng phần mềm, ngăn xếp là “xương sống” của các tính năng:
- Undo/Redo: Các hành động của người dùng được lưu vào ngăn xếp. Khi nhấn Undo, trạng thái cuối cùng bị lấy ra (pop) để khôi phục.
- Duyệt đồ thị (DFS): thuật toán duyệt theo chiều sâu sử dụng ngăn xếp để theo vết các đỉnh đã đi qua.
- Xử lý biểu thức: Chuyển đổi từ trung tố (Infix) sang hậu tố (Postfix) và tính toán giá trị biểu thức toán học.
Giải thuật xử lý hậu tố bằng ngăn xếp
Một trong những bài toán kinh điển nhất minh họa sức mạnh của cấu trúc dữ liệu stack là tính toán biểu thức hậu tố. Ở dạng này, toan tử nằm sau các toán hạng (Ví dụ: 3 4 + tương đương 3 + 4).
Quy trình thực hiện thuật toán:
- Duyệt biểu thức từ trái sang phải.
- Nếu gặp toán hạng (số): đẩy vào (push) ngăn xếp.
- Nếu gặp toán tử (+, -, , /):
- lấy ra (pop) hai toán hạng từ ngăn xếp (gọi là
avàb). - Thực hiện phép tính:
b (toán tử) a. - đẩy vào (push) kết quả vừa tính ngược lại ngăn xếp.
- lấy ra (pop) hai toán hạng từ ngăn xếp (gọi là
- Kết thúc biểu thức, phần tử cuối cùng còn lại trong ngăn xếp chính là kết quả.
Sử dụng ngăn xếp giúp máy tính không cần quan tâm đến độ ưu tiên của dấu ngoặc, vì cấu trúc hậu tố đã tự bao hàm thứ tự thực thi một cách logic và tuyến tính.
Những sai lầm thường gặp và lời khuyên chuyên gia
Qua nhiều năm phát triển phần mềm, tôi nhận thấy các lập trình viên thường mắc một số lỗi tư duy khi làm việc với cấu trúc dữ liệu stack:
- Quên kiểm tra isEmpty: Đây là lỗi phổ biến nhất dẫn đến các ngoại lệ Runtime. Luôn đảm bảo bạn đã kiểm tra trạng thái ngăn xếp trước khi gọi lệnh lấy ra (pop).
- Lạm dụng đệ quy thay vì ngăn xếp tường minh: Đệ quy hệ thống có giới hạn bộ nhớ rất hẹp (thường chỉ vài MB). Với các bài toán có độ sâu lớn, hãy tự xây dựng một cấu trúc dữ liệu stack trên Heap để tránh crash chương trình.
- Chọn sai kiểu dữ liệu: Trong Java,
java.util.Stacklà một lớp cũ (legacy) và có tính chấtsynchronizedgây chậm hiệu năng. Các chuyên gia khuyến nghị sử dụngjava.util.Deque(với triển khaiArrayDeque) để đạt hiệu năng tối ưu nhất trong môi trường đơn luồng.
Việc nắm vững cấu trúc dữ liệu stack không chỉ là nắm vững một cách lưu trữ dữ liệu, mà là nắm vững tư duy điều phối dòng chảy thông tin trong hệ thống. Hãy thực hành cài đặt lại các thao tác trên bằng nhiều ngôn ngữ khác nhau để thấm nhuần nguyên lý quản lý con trỏ và bộ nhớ.
Tham khảo:
- Oracle Java Documentation:
java.util.Dequeinterface specification. - NIST Data Structure Definitions: “Stack” in Dictionary of Algorithms and Data Structures.
- Robert Sedgewick & Kevin Wayne: “Algorithms, 4th Edition”, Section 1.3: Stacks and Queues.
Cập nhật lần cuối 01/03/2026 by Hiếu IT
