Chào các bạn!
Hẳn các bạn đã từng nghe tới thuật ngữ Stack trong tin học. Nó được hiểu là Ngăn Xếp. Ngăn xếp là một kiểu danh sách tuyến đặc biệt mà phép bổ sung hoặc loại bỏ phần tử luôn thực hiện tại một đầu, gọi là đỉnh (top). Ta có thể hình dung Stack như việc xếp chồng đĩa: ta chồng thêm 1 đĩa ở trên cùng, và lấy ra 1 đĩa cũng ở trên cùng. Stack thuộc và loại danh sách hoạt động dựa trên nguyên tắc LIFO (Last - In - First - Out).
Các thao tác trên Stack: (dựa trên Stack để lưu trữ số nguyên)
1. Khai báo Stack:
#define TRUE 1
#define FALSE 0
#define MAX 100
typedef struct {
int top;
int nodes[MAX];
} stack;
2. Thao tác Empty (kiểm tra tính rỗng của Stack):
int Empty(stack *ps) {
if (ps -> top == -1)
return (TRUE);
return (FALSE);
}
3. Thêm nút mới vào đỉnh Stack (Push):
void Push (stack *ps, int x) {
if ( ps -> top == -1) {
printf(\n stack full);
return;
}
ps -> top = ps ->top + 1;
ps -> nodes[ps->top] = x;
}
4. Thao tác kiểm tra tính đầy của Stack (Full):
int Full(stack *s) {
if (s -> top == (MAX-1)) return 1;
else return 0;
}
5. Thao tác lấy một phần tử từ đỉnh Stack (Pop):
int Pop (stack *s) {
if (Empty(s)) {
printf("\n Stack rong");
return NULL;
}
return (s -> info[s->top--]);
}
Ứng dụng của Stack: Có rất nhiều ứng dụng của Stack, sau đây tớ chỉ giới thiệu một số ứng dụng nhỏ.
1. Đảo ngược xâu: Ta sẽ nhập xâu vào Stack, sau đó lấy lần lượt các phần tử của Stack ra tại đỉnh của nó. Và do đó ta có xâu đã đảo ngược.
2. Đổi một số n từ hệ cơ số thập phân sang hệ nhị phân: Ta sẽ lấy số dư n%2 lưu vào Stack, và gán n=n/2. Đến khi nào n=1 thì cũng lưu vào Stack. Ta lại lấy lần lượt các phần tử của Stack => xâu biểu diễn nhị phân của n.
3. Thao tác trên Stack tổng quát cùng với các thao tác duyệt Stack, tìm kiếm trên stack có rất nhiều ứng dụng.