Một 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 hầu hết các ngôn ngữ lập trình. Được đặt tên là "ngăn xếp" vì hoạt động của nó tương tự như một ngăn xếp trong cuộc sống hàng ngày, chẳng hạn như cách chúng ta xếp bài hoặc đĩa lên nhau.
Trong cuộc sống thực, ngăn xếp chỉ cho phép thao tác trên phần tử ở trên cùng. Ví dụ, chúng ta chỉ có thể đặt hoặc thêm một lá bài hoặc đĩa lên trên cùng của ngăn xếp. Do đó, cấu trúc dữ liệu ngăn xếp chỉ cho phép thao tác trên phần tử ở vị trí trên cùng. Mọi lúc, chúng ta chỉ có thể truy cập vào phần tử ở trên cùng của ngăn xếp.
Điều này biến ngăn xếp thành một cấu trúc dữ liệu dạng LIFO (Last-In-First-Out), nghĩa là phần tử được đặt vào cuối cùng sẽ được truy cập đầu tiên. Trong ngăn xếp, việc thêm phần tử được gọi là hoạt động PUSH, còn việc xóa phần tử được gọi là hoạt động 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.
Ngăn xếp có thể được triển khai bằng cách sử dụng mảng (Array), cấu trúc (Struct), con trỏ (Pointer) và danh sách liên kết (Linked List). Ngăn xếp có thể có kích thước cố định hoặc có thể thay đổi kích thước. Trong phần tiếp theo, chúng ta sẽ tìm hiểu về việc triển khai ngăn xếp bằng cách sử dụng mảng.
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 quan trọng liên quan đến khái niệm là push() và pop().
Hoạt động push() dùng để thêm một phần tử vào ngăn xếp, trong khi hoạt động pop() dùng để xóa một phần tử khỏi ngăn xếp.
Ngăn xếp cũng có một số tính năng hỗ trợ như peek(), isFull() và isEmpty(). Hoạt động peek() trả về phần tử ở trên cùng của ngăn xếp mà không xóa phần tử đó. Hoạt động isFull() kiểm tra xem ngăn xếp đã đầy hay chưa, và hoạt động isEmpty() kiểm tra xem ngăn xếp có trống hay không.
Trong 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 thường được gọi là top và biểu diễn 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 xóa.
Phương thức peek() của ngăn xếp
Phương thức peek() được sử dụng để lấy phần tử ở trên cùng của ngăn xếp mà không xóa phần tử này. Dưới đây là giải thuật và triển khai của phương thức peek() trong ngôn ngữ C:
int peek() { return stack[top]; }Phương thức isFull() của ngăn xếp
Phương thức isFull() được sử dụng để kiểm tra xem ngăn xếp đã đầy hay chưa. Dưới đây là giải thuật và triển khai của phương thức isFull() trong ngôn ngữ C:
bool isfull() { if(top == MAXSIZE) return true; else return false; }Phương thức isEmpty() của ngăn xếp
Phương thức isEmpty() được sử dụng để kiểm tra xem ngăn xếp có trống hay không. Dưới đây là giải thuật và triển khai của phương thức isEmpty() trong ngôn ngữ C:
bool isempty() { if(top == -1) return true; else return false; }Hoạt động PUSH trong ngăn xếp
Hoạt động PUSH dùng để thêm một phần tử mới vào ngăn xếp. Hoạt động này bao gồm các bước sau:
- Kiểm tra xem ngăn xếp đã đầy hay chưa.
- Nếu ngăn xếp đã đầy, tiến trình bị lỗi và thoát ra.
- Nếu ngăn xếp chưa đầy, tăng top lên để trỏ tới vị trí bộ nhớ trống tiếp theo.
- Thêm phần tử vào vị trí mà top đang trỏ đến trên ngăn xếp.
- Trả về thành công.
Nếu ngăn xếp được triển khai bằng danh sách liên kết, thì ở bước 3 chúng ta cần cấp phát một không gian động.
Dưới đây là giải thuật và triển khai của hoạt động PUSH trong ngôn ngữ C:
void push(int data) { if(!isFull()) { top = top + 1; stack[top] = data; } else { printf("Khong the chen them du lieu vi Stack da day.\n"); } }Hoạt động POP của ngăn xếp
Hoạt động POP dùng để truy cập và xóa phần tử khỏi ngăn xếp. Trong triển khai mảng, phần tử không bị xóa, thay vào đó top giảm để trỏ tới phần tử tiếp theo. Trong triển khai danh sách liên kết, phần tử thực sự bị xóa và được giải phóng khỏi bộ nhớ.
Hoạt động POP bao gồm các bước sau:
- Kiểm tra xem ngăn xếp có trống hay không.
- Nếu ngăn xếp trống, tiến trình bị lỗi và thoát ra.
- Nếu ngăn xếp không trống, truy cập phần tử ở trên cùng của ngăn xếp.
- Giảm top đi 1.
- Trả về giá trị của phần tử đã bị xóa.
Dưới đây là giải thuật và triển khai của hoạt động POP trong ngôn ngữ C:
int pop(int data) { if(!isempty()) { data = stack[top]; top = top - 1; return data; } else { printf("Khong the lay du lieu, Stack la trong.\n"); } }Ứng dụng của ngăn xếp
Ngăn xếp có nhiều ứng dụng quan trọng trong lập trình. Dưới đây là một số ví dụ về việc sử dụng ngăn xếp:
- Xử lý gọi hàm trong C/C++
- Trong máy tính, sử dụng để tính giá trị biểu thức, xử lý ngắt
- Trong các chương trình biên dịch
- Trong trình duyệt web, trình soạn thảo văn bản
- Định giá biểu thức
Với việc duyệt biểu thức hậu tố và chuyển đổi biểu thức dạng trung tố sang hậu tố, ngăn xếp trở thành một công cụ hữu ích trong việc xử lý các biểu thức số học phức tạp.
Trên đây là những điểm cơ bản về ngăn xếp, cấu trúc dữ liệu quan trọng trong lập trình. Hy vọng bạn đã hiểu và có thêm kiến thức về ngăn xếp sau bài viết này.
