Giới thiệu
Ngăn xếp là một cấu trúc dữ liệu trừu tượng (Abstract Data Type - ADT) phổ biến trong lập trình. Tên "ngăn xếp" được đặt vì nó hoạt động tương tự như một ngăn xếp trong cuộc sống thực, ví dụ như một cỗ bài hay một chồng đĩa (tiếng Việt).
Trong cuộc sống thực, ngăn xếp chỉ cho phép các hoạt động trên đỉnh ngăn xếp. Ví dụ, chúng ta chỉ có thể đặt hoặc thêm một lá bài hay một cái đĩa vào đỉnh ngăn xếp. Tương tự, cấu trúc dữ liệu ngăn xếp chỉ cho phép các thao tác dữ liệu trên đỉnh ngăn xếp. Tại mọi thời điểm, chúng ta chỉ có thể truy cập phần tử trên cùng của ngăn xếp.
Đặc điểm này làm cho ngăn xếp trở thành cấu trúc dữ liệu dạng "ngăn xếp hợp lệ cuối cùng vào đầu tiên ra" (LIFO - Last-In-First-Out). Nghĩa là phần tử cuối cùng được thêm vào ngăn xếp sẽ được truy cập đầu tiên khi loại bỏ. Trong thuật ngữ ngăn xếp, hoạt động thêm phần tử được gọi là "PUSH" và hoạt động loại bỏ phần tử được gọi là "POP".
Biểu diễn cấu trúc dữ liệu ngăn xếp
Dưới đây là sơ đồ minh họa một ngăn xếp và các hoạt động diễn ra trên ngăn xếp.
Một ngăn xếp có thể được triển khai bằng mảng, cấu trúc, con trỏ hoặc danh sách liên kết. Ngăn xếp có thể có kích thước cố định hoặc có thể thay đổi kích thước. Dưới đây là triển khai ngăn xếp sử dụng mảng và các ngăn xếp cố định.
Các hoạt động cơ bản trên ngăn xếp
Các hoạt động cơ bản trên ngăn xếp liên quan đến việc khởi tạo, sử dụng và xóa ngăn xếp. Ngoài ra, ngăn xếp còn có hai hoạt động liên quan đến khái niệm, đó là:
- Hoạt động PUSH: thêm một phần tử vào ngăn xếp.
- Hoạt động POP: loại bỏ một phần tử từ ngăn xếp.
Ngoài các hoạt động cơ bản này, ngăn xếp cũng hỗ trợ một số tính năng khác, bao gồm:
- Hoạt động PEEK: lấy phần tử trên cùng của ngăn xếp mà không xóa nó.
- Hoạt động isFull(): kiểm tra xem ngăn xếp đã đầy hay chưa.
- Hoạt động isEmpty(): kiểm tra xem ngăn xếp có trống hay không.
Tại mọi thời điểm, chúng ta duy trì một con trỏ tới phần tử cuối cùng được thêm vào ngăn xếp. Con trỏ này luôn biểu diễn vị trí trên cùng của ngăn xếp và được gọi là "đỉnh ngăn xếp" (top). Điều này cho phép chúng ta truy cập phần tử trên cùng của ngăn xếp mà không cần thực hiện hoạt động loại bỏ.
Ứng dụng của ngăn xếp
Ngăn xếp có rất nhiều ứng dụng trong lập trình. Dưới đây là một số ví dụ:
- Xử lý gọi hàm trong C/C++
- Tính giá trị biểu thức
- Xử lý ngắt trong máy tính
- Triển khai trình duyệt web và trình soạn thảo văn bản
- Định giá biểu thức
- Chuyển đổi biểu thức từ dạng trung tố sang hậu tố
Ngăn xếp là một cấu trúc dữ liệu quan trọng và hữu ích trong lập trình. Hi vọng bài viết này đã giúp bạn hiểu thêm về ngăn xếp và ứng dụng của nó.
(Source: Tutorialspoint)
