Stack – Ngan Xep

Giới thiệu:

Chúng ta có thể hình dung một cách đơn giản như hình ảnh một chồng đĩa, đĩa nào
được đặt vào chồng sau cùng sẽ nằm trên tất cả đĩa khác và sẽ được lấy ra đầu tiên. Vì
nguyên tắc vào sau ra trước đó, Stack còn có tên gọi là danh sách kiểu LIFO (Last In First Out). Vị trí cuối cùng được gọi là đỉnh (top) của ngăn xếp.

Hai thao tác chính trên Stack là:
1. Thao tác push: đưa một phần tử vào đỉnh của Stack
2. Thao tác pop: xoá đi một phần tử ở đỉnh của Stack.

Cài đặt Stack dùng CTDL mảng:

Chúng ta sẽ cài đặt một Stack dùng cấu trúc dữ liệu mảng. Để cho tổng quát ta gọi Data là kiểu dữ liệu được định nghĩa mà Stack lưu trữ, ví dụ Data có thể
là số nguyên, thực... hoặc một cấu trúc dữ liệu nào đó:
typedef int Data
typedef float Data
typedef struct {
int ID;
char Name[50];
float Salary;
...
} Data;
...

Khai báo cấu trúc dữ liệu Stack trên mảng:

#define MAX 100
typedef struct{
int top;
Data S[MAX];
} Stack;



Trong cấu trúc Stack này các trường có ý nghĩa như sau:
 top: chỉ đến đỉnh của Stack, top = -1 Þ Stack rỗng, top ³ 0 Þ Stack có phần tử
 S[MAX]: chứa dữ liệu của Stack lưu trữ, để truy cập đến phần tử đỉnh thì dùng
trường top.

Các thao tác trên Stack được mô tả như sau:

 void Push(Stack &st, Data x): Đưa một phần tử x vào đỉnh của Stack.
 Data Pop(Stack &st): Lấy một phần tử ở đỉnh ra khỏi Stack.
 void InitStack(Stack &st): Hàm khởi tạo một Stack mới rỗng
 int IsEmpty(Stack st): Kiểm tra xem Stack có rỗng hay không.
 int IsFull(Stack st): Kiểm tra xem Stack đầy hay chưa.
 Data Top(Stack st): Xem một phần tử ở đỉnh (không lấy ra).

Cài đặt của các thao tác:

#define TRUE 1
#define FALSE 0
void Push(Stack &st, Data x)
{
if (IsFull(st))
{
printf(“\nStack full!”);
}
else
st.S[++st.top] = x;
}
Data Pop(Stack &st)
{
if (IsEmpty(st))
printf(“\nStack empty!”);
else
return (st.S[st.top--]);
}



void InitStack(Stack &st)
{
st.top = -1;
}
int IsEmpty(Stack st)
{
if (st.top == -1)
return TRUE;
else
return FALSE;
}
int IsFull(Stack st)
{
if (st.top >= MAX)
return TRUE;
else
return FALSE;
}
Data Top(Stack st)
{
Data d;
if (IsEmpty(st))
printf(“\n Stack empty!”);
else
d = st.S[st.top];
return d;
}

Các ứng dụng stack:

Thông thường cấu trúc dữ liệu stack thích hợp cho việc lưu trữ dữ liệu mà trình tự

truy xuất ngược với trình tự lưu trữ. Có nghĩa là dữ liệu lưu trữ trước sẽ được lấy ra sau

những dữ liệu lưu sau (LIFO). Do đó stack có một số ứng dụng như sau:

 Trong trình biên dịch, stack dùng để lưu trữ các lời gọi hàm, ví dụ như

hàm A gọi hàm B, hàm B lại gọi hàm C, khi hàm C thực hiện xong thì sự điều khiển

chương trình sẽ trở về thực hiện chương trình B. Rồi khi hàm B thực hiện xong thì sự

điều khiển chương trình sẽ được trả về cho A. Khi đó ta thấy là hàm C được gọi sau

cùng và chúng được thực hiện xong trước tiên rồi mới đến B và A. Đây là dạng thực

hiện sau và kết thúc trước.

 Lưu trữ dữ liệu để giải các bài toán lý thuyết đồ thị. Ví dụ như tìm chu

trình Euler, tìm đường đi...

 Ngoài ra, stack còn được sử dụng để khử một số bài toán đệ quy.

 Còn rất nhiều ứng dụng của Stack...