4/28/2010
Chương 7. Bài 2. Stack
ĐỖ BÁ LÂM ViỆN CNTT&TT, TRƯỜNG ĐHBK HÀ NỘI
Nội dung
1. Khái niệm stack
2. Xây dựng stack
2.1. Sử dụng mảng
2.2. Sử dụng danh sách liên kết
2
1. Khái niệm stack
Stack (ngăn xếp)
Là một cấu trúc dữ liệu mà các
thao tác xử lý chỉ được thực hiện ở phía đáy (cuối) của nó
Cấu trúc dạng LIFO (Last In First
Out) – “Vào sau ra trước”
Thao tác xử lý
• Đẩy vào PUSH
• Lấy ra POP
3
1
4/28/2010
1. Khái niệm stack
Đỉnh
Đáy
1. Khái niệm stack
Push(B)
Pop()
Pop()
Push(A)
A B
A B
Stack rỗng
Stack lại rỗng
Stack có 1 phần tử: A
Stack có 2 phần tử: A B
Stack còn 1 phần tử: A
B A A A
Ứng dụng của Stack
Lưu trữ các trang web đã từng được duyệt
trên Web browser
Cài đặt thao tác Undo trong các phần mềm
soạn thảo
Lưu danh sách các lời gọi hàm trong Java
Virtual Machine
2
4/28/2010
Ghi nhớ
Stack được hình dung như một ngăn xếp chứa các quyển sách với 2 thao tác đưa vào và lấy ra theo nguyên tắc:
Quyển sách nào được đưa vào sau sẽ lấy ra
trước – LIFO (Last In First Out)
Ví dụ - Bài toán chuyển cơ số
Nguyên tắc đổi một số nguyên từ thập
phân sang nhị phân:
Các số dư lấy ra sau được hiển thị trước
Cơ chế sắp xếp của Stack
Giải pháp
Dùng stack để lưu trữ số dư qua từng
phép chia:
Khi thực hiện phép chia: Đưa số dư vào
Stack
Khi hiển thị kết quả: Lấy chúng lần lượt từ
Stack
3
4/28/2010
Giải pháp
1
1 1 1 PUSH 0 0 0 PUSH 0 0 0 0
1
1
1 0 0 1 POP 0 0 0 0 0 0 0
Giải thuật
1. Nhap N
2. while N != 0
R = N% 2; //Tính số dư trong phép chia N cho 2
PUSH (S, R); //Đẩy R vào đỉnh Stack S
N=N/2; //Thay N bằng N/2
3. while S chưa rỗng
POP(S,R); //Lấy phần tử từ stack đưa vào R
Hien_thi R;
2. Xây dựng Stack
Lưu trữ được các đối tượng dữ liệu (quyển
sách)
Xây dựng 2 thao tác Push và Pop theo
nguyên tắc LIFO
Có hai cách cài đặt stack
Sử dụng mảng
Sử dụng danh sách liên kết
4
4/28/2010
2.1. Sử dụng mảng
Mỗi phần tử của stack được lưu như một phần tử của
mảng
Đáy: phần tử có chỉ số 0
Đỉnh: phần tử được đưa vào cuối cùng, có chỉ số T
Khởi tạo T=-1
Stack rỗng (empty) T = -1, stack đầy T = MAX-1
Đáy Stack
13
2.1. Sử dụng mảng
#define MAX 100 //So phan tu lon nhat
cua Stack
//Khai bao Stack va T la 2 bien toan cuc
ElemType Stack[MAX];
int T=-1;
14
2.1. Sử dụng mảng
Stack được biểu diễn thông qua mảng S[MAX]
int push(ElemType N){
if (T==MAX-1) return 0;
else{ //mảng chưa đầy
T++;
S[T]=N;
}
return 1;
}
5
4/28/2010
2.1. Sử dụng mảng
int pop(ElemType *N){
if (T== -1)
return 0;
else{
*N = S[T--];
return 1;
}
}
2.2. Sử dụng danh sách liên kết
Stack là cấu trúc LIFO (Last In First Out)
Thao tác Push, Pop?
Head
17
2.2. Sử dụng danh sách liên kết
Push
Thêm một nút vào đầu danh sách
Pop
Lấy giá trị nút đầu tiên trong danh sách
Loại bỏ nút này khỏi danh sách
18
6
4/28/2010
2.2. Sử dụng danh sách liên kết
struct node {
ElemType data;
struct node *next;
};
//Khai báo con trỏ đầu là biến toàn cục
struct node *top;
Push
void push(ElemType N) {
struct node *temp;
temp=(struct node *) malloc(sizeof(struct node));
temp->data = N;
Temp top 45 7
temp->next = top;
top = temp;
1
}
8 \
Push
void push(ElemType N) {
struct node *temp;
temp=(struct node *) malloc(sizeof(struct node));
temp->data = N;
Temp top 45 7
temp->next = top;
top = temp;
1
}
8 \
7
4/28/2010
Push
void push(ElemType N) {
struct node *temp;
temp=(struct node *) malloc(sizeof(struct node));
temp->data = N;
Temp top 45 7
temp->next = top;
top = temp;
1
}
8 \
Pop
top
else{
45 Temp int pop(ElemType *N){ struct node *temp; if(top==NULL) return 0; 7
*N = top->data; temp = top; top = top->next; free(temp); return 1;
}
}
8 \
1
Giá trị của thành phần top cần lưu lại trước khi giải phóng vùng nhớ
Pop
else{
top 45 Temp int pop(ElemType *N){ struct node *temp; if(top==NULL) return 0; 7
*N = top->data; temp = top; top = top->next; free(temp); return 1;
}
}
1
8 \
8
4/28/2010
Pop
top
else{
Temp int pop(ElemType *N){ struct node *temp; if(top==NULL) return 0; 7
*N = top->data; temp = top; top = top->next; free(temp); return 1;
}
}
1
8 \
Bài toán
Demo dS_Array.c, dS_List.c
Bài tập 1.
Viết chương trình chuyển một số nguyên
dương từ hệ cơ số 10 sang hệ cơ số 2 sử dụng stack (bằng mảng và danh sách liên kết)
Bài toán
Bài tập 2. Cộng hai số nguyên lớn
Kiểu dữ liệu số nguyên chỉ biểu diễn số trong
phạm vi nhất định
Mục đích: thực hiện thao tác cộng, trừ, nhân, chia trên các số nằm ngoài phạm vi biểu diễn
27
9
4/28/2010
Bài toán
Thực hiện phép cộng trên hai số nguyên
“lớn”
Hai số được lưu dưới dạng xâu kí tự
28
Bài toán
Cải tiến
Trong cách xây dựng stack bằng mảng, thay
vì tách rời mảng và biến T chúng ta định nghĩa một cấu trúc gồm 2 trường là mảng và biến T này
Áp dụng làm lại các bài tập ở trên.
