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;
}