Giảng viên: TS. Ngo Huu Phuc
Tel: 0438 326 077
Mob: 098 5696 580
Email: ngohuuphuc76@gmail.com
Cấu trúc dữ liệu và giải thuật
Bài 10: Ứng dụng của ngăn xếp
PhD. Ngo Huu Phuc, Le Quy Don Technical University
1
Bài 10. Một vài ứng dụng của Stack
Nội dung:
10.1. Đảo mảng (3)
10.2. Đảo chuỗi (4)
10.3. Chuyển đổi hệ số (9)
10.4. Bracket Matching (5)
10.5. Balancing Act (4)
Tham khảo:
1. Data structures and Algorithms Stacks.htm
2. Kyle Loudon Mastering Algorithms, Chapter 6 Stacks and Queues
3. Elliz Horowitz –Fundamentals of Data Structures, Chapter 3 Stacks and
Queues
4. Deshpande Kakle –C and Data Structures, Chapter 19. Stacks and
Queues
5. Bài giảng TS Nguyễn Nam Hồng
PhD. Ngo Huu Phuc, Le Quy Don Technical University
2
10.1. Đảo mảng (1/3)
Cho một mảng gồm một dãy các giá trị.
Để đảo thứ tự các phần tử trong mảng, sử dụng
nguyên lý Last-In-First-Out của Stack.
Ví dụ về hoạt động của đảo mảng:
PhD. Ngo Huu Phuc, Le Quy Don Technical University
3
17
23
25
18
18
25
23
17
134
47
55
216
216
55
47
134
10.1. Đảo mảng (2/3)
Ý tưởng thực hiện giải thuật:
1. Khởi tạo một Stack rỗng, có kiểu số.
2. Với n phần tử của mảng, lần lượt đưa vào Stack
thông qua hàm Push:
Push a[i] in to Stack.
3. Lần lượt lấy ra từ Stack n phần tử và đưa vào trở
lại mảng ban đầu:
Pop a item from nStack in to a[i].
4. Kết thúc giải thuật.
PhD. Ngo Huu Phuc, Le Quy Don Technical University
4
10.1. Đảo mảng (3/3)
Ví dụ về đảo mảng:
void revArray(int a[],int n,int stack[])
{
makeEmpty(stack);
for(int i=0;i<n;i++)
push(stack,a[i]);
for(int i=0;i<n;i++)
a[i]=pop(stack);
}
PhD. Ngo Huu Phuc, Le Quy Don Technical University
5