1.Cấu trúc dữ liệu ngăn xếp stack là gì?

Cấu trúc ngăn xếp stack là một cấu trúc dữ liệu trừu tượng với nguyên lý hoạt động LIFO – với ý nghĩa là vào cuối thì được ra đầu.

Một cấu trúc ngắn xếp stack hoàn toàn có thể được tưởng tượng rằng stack như một hộp chứa, trong đó các phần tử có thể coi là các Node. Các thao tác với phần tử trong hộp chứa đó chỉ có thể thao tác ở phần đầu.

Trong cấu trúc dữ liệu ngăn xếp stack ta có 2 thao tác chính đó là:

  • Thao tác push
  • Thao tác pop

Push là việc thêm một phần tử (hay một Node) vào phần đỉnh của ngăn xếp.

Pop là việc lấy ra và thực hiện xóa một phần tử (hay một Node) ở phần đỉnh của ngăn xếp.

Trong quá trình cài đặt stack bằng mảng một chiều hoặc cài đặt stack bằng danh sách liên kết sẽ có thêm một số thao tác nữa. Tuy nhiên, ta sẽ đi chi tiết vào những bài tiếp theo.

2.Cấu trúc ngăn xếp stack với mảng

Ta hoàn toàn có thể tạo một stack bằng cách khai báo một mảng 1 chiều với kích thước tối đa là N phần tử. Ví dụ N = 100

Các phần tử của stack trong mảng một chiều được đánh thứ tự từ 0 đến N – 1.

Phần tử nằm ở đầu stack sẽ có chỉ số Top (lúc đó trong stack đang chứa Top +1 phần tử)

Để khai báo một stack bằng mảng, ta cần một mảng 1 chiều A[MAX] và cần khai báo biến int top để cho biết chỉ số của đầu stack và hằng số MAX cho biết kích thước tối đa của stack. Xem code dưới đây để hiểu rõ hơn việc khai báo stack với mảng chứa dữ liệu số nguyên int A[MAX]

#define MAX 100
struct stack{
    int top;
    int A[MAX];
};
typedef struct stack STACK;

Việc khai báo int A[MAX] là do stack của tôi mặc định đang cài đặt để lưu trữ cho dữ liệu có kiểu số nguyên nên kiểu dữ liệu của mảng A sẽ là int. Một số bài toán khác nhau ta có thể thay đổi int thành kiểu dữ liệu khác phù hợp với bài toán.

Đoạn code ở trên chỉ dừng lại ở việc khai báo stack bằng mảng một chiều, các thao tác chi tiết với cấu trúc dữ liệu stack cài đặt bằng mảng sẽ được nêu rõ hơn ở bài sau!

3.Cấu trúc stack với danh sách liên kết

Việc cài đặt cấu trúc dữ liệu stack với mảng một chiều cho ta khá nhiều ưu điểm như: Các thao tác trên đều làm việc với chi phí O(1), việc cài đặt stack thông qua mảng một chiều đơn giản và khá hiệu quả.

Tuy nhiên, khi cài đặt stack bằng mảng lại tồn tại một số hạn chế nhất định như: Giới hạn về kích thước của stack N, giá trị của N có thể quá nhỏ so với nhu cầu thực tế hoặc quá lớn sẽ làm lãng phí bộ nhớ.

Vì vậy việc cài đặt stack với danh sách liên kết ra đời nhằm khắc phục các hạn chế của việc cài đặt stack bằng mảng.

Khi cài đặt stack bằng danh sách liên kết thì các phần tử cũng chính là một node trong đó sẽ có 2 thành phần là data và con trỏ next. Xem đoạn code dưới đây để hiểu hơn về việc khai báo một Node trong stack chứa kiểu dữ liệu số nguyên int data 

struct node{
    int data;
    node *next;
};
typedef struct node NODE;

Vì stack chỉ thao tác với phần tử ở trên đỉnh của nó (hay còn gọi là phần tử Top) nên việc khai báo stack với danh sách liên kết chỉ đơn giản là việc khai báo một kiểu dữ liệu stack với một NODE *top;

struct stack{
    NODE *top;
};
typedef struct stack STACK;

2 đoạn code ở trên vẫn chỉ là bước đầu cho việc khai báo cấu trúc stack với danh sách liên kết, các bài sau tôi sẽ nêu rõ hơn về các thao tác của danh sách liên kết đối với cấu trúc stack. Mời bạn đọc chú ý đón xem!

4.Một số ứng dụng của cấu trúc dữ liệu stack

Stack thích hợp lưu trữ các loại dữ liệu mà trình tự truy xuất ngược với trình tự lưu trữ. Một số ứng dụng của Stack:

  • Trong trình biên dịch (thông dịch), khi thực hiện các thủ tục, Stack được sử dụng để lưu môi trường của các thủ tục.
  • Lưu dữ liệu khi giải một số bài toán của lý thuyết đồ thị (như tìm đường đi)
  • Khử đệ qui