Bài giảng Cấu trúc dữ liệu - Chương 7: Stack - Queue trình bày về khái niệm, các thao tác, hiện thực, ứng dụng của ngăn xếp (stack) và hàng đợi (queue). Đây là tài liệu tham khảo thuộc chuyên ngành Công nghệ thông tin.
AMBIENT/
Chủ đề:
Nội dung Text: Bài giảng Cấu trúc dữ liệu: Chương 7 - Nguyễn Xuân Vinh
- GV: NGUYỄN XUÂN VINH
CẤU TRÚC DỮ LIỆU
DATA STRUCTURES
[214331]
STACK - QUEUE
MÔN: CẤU TRÚC DỮ LIỆU
Teacher: Nguyễn Xuân Vinh
6/12/14
Email:
nguyenxuanvinh@hcmuaf.edu.
/XX
vn
1
- 2 /XX 6/12/14 MÔN: CẤU TRÚC DỮ LIỆU GV: NGUYỄN XUÂN VINH
•
•
Hàng đợi
Ngăn xếp
Nội dung
- GV: NGUYỄN XUÂN VINH
Nội dung
Ngăn xếp (Stack)
Khái niệm Stack
Các thao tác trên Stack
Hiện thực Stack
MÔN: CẤU TRÚC DỮ LIỆU
Ứng dụng của Stack
Hàng đợi
6/12/14
/XX
3
- GV: NGUYỄN XUÂN VINH
Stack - Khái niệm
•
Stack là một danh sách mà các đối tượng được thêm vào và lấy
ra chỉ ở một đầu của danh sách
•
Vì thế, việc thêm một đối tượng vào Stack hoặc lấy một đối
tượng ra khỏi Stack được thực hiện theo cơ chế LIFO (Last In
First Out - Vào sau ra trước)
MÔN: CẤU TRÚC DỮ LIỆU
•
Các đối tượng có thể được thêm vào Stack bất kỳ lúc nào nhưng
chỉ có đối tượng thêm vào sau cùng mới được phép lấy ra khỏi
Stack
6/12/14
/XX
4
- 5 /XX 6/12/14 MÔN: CẤU TRÚC DỮ LIỆU GV: NGUYỄN XUÂN VINH
Các phép toán cần có trên Stack
- GV: NGUYỄN XUÂN VINH
Stack – Các thao tác
6
•
Stack hỗ trợ 2 thao tác chính:
“Push”: Thao tác thêm 1 đối tượng vào Stack
“Pop”: Thao tác lấy 1 đối tượng ra khỏi
Stack
MÔN: CẤU TRÚC DỮ LIỆU
Ví dụ:
532--4
Push Pop
3
6/12/14
4
2
/XX
5
6
- GV: NGUYỄN XUÂN VINH
Stack – Các thao tác
7
•
Stack cũng hỗ trợ một số thao tác khác:
–
isEmpty(): Kiểm tra xem Stack có rỗng
không
MÔN: CẤU TRÚC DỮ LIỆU
–
Top(): Trả về giá trị của phần tử nằm ở đầu
Stack mà không hủy nó khỏi Stack. Nếu
Stack rỗng thì lỗi sẽ xảy ra
6/12/14
/XX
7
- GV: NGUYỄN XUÂN VINH
Hiện thực Stack
8
Mảng 1 chiều Danh sách LK
Kích thước stack Danh
khi quá thiếu, lúc sách liên
MÔN: CẤU TRÚC DỮ LIỆU
quá thừa kết!
6/12/14
Push/Pop
khá dễ
Push / Pop
dàng
hơi phức tạp
/XX
8
- GV: NGUYỄN XUÂN VINH
Hiện thực Stack dùng mảng
9 •
Có thể tạo một Stack bằng cách khai báo một mảng
1 chiều với kích thước tối đa là N (ví dụ: N =1000)
–
Stack có thể chứa tối đa N phần tử đánh số từ 0
đến N-1
MÔN: CẤU TRÚC DỮ LIỆU
•
Phần tử nằm ở đỉnh Stack sẽ có chỉ số là top (lúc
đó trong Stack đang chứa top+1 phần tử)
•
Như vậy, để khai báo một Stack, ta cần một mảng
1 chiều list, và 1 biến số nguyên top cho biết chỉ số
của đỉnh Stack:
class Stack {
6/12/14
int list[] = new int[N];
/XX
int top;
9
- GV: NGUYỄN XUÂN VINH
Hiện thực Stack dùng mảng
10
•
Ngăn xếp được cài đặt bằng mảng phải có:
–
Một biến top dùng để lưu vị trí con trỏ hiện tại.
–
Một mảng dùng để lưu giá trị của ngăn xếp.
Khởi tạo ngăn xếp rỗng:
MÔN: CẤU TRÚC DỮ LIỆU
•
–
Ngăn xếp rỗng là ngăn xếp không chứa bất kỳ
phần tử nào Đỉnh ngăn xếp không trỏ tới phần
tử nào.
•
Kiểm tra ngăn xếp rỗng:
–
Ngăn xếp rỗng khi top = -1
•
Kiểm tra ngăn xếp đầy:
6/12/14
–
Ngăn xếp đầy khi top = max – 1
/XX
10
- GV: NGUYỄN XUÂN VINH
Hiện thực Stack dùng mảng
•
Thêm một phần tử vào ngăn xếp:
–
Kiểm tra ngăn xếp đầy
–
Top tăng lên 1 đơn vị
–
Phần tử tại vị trí top bây giờ sẽ là phần tử cần thêm vào.
MÔN: CẤU TRÚC DỮ LIỆU
•
Lấy một phần tử trong ngăn xếp:
–
Kiểm tra ngăn xếp rỗng
–
Trả về phần tử tại vị trí top.
•
Xóa 1 phần tử khỏi ngăn xếp:
–
Kiểm tra ngăn xếp rỗng.
–
Top giảm đi 1 đơn vị.
6/12/14
/XX
11
- GV: NGUYỄN XUÂN VINH
Hiện thực Stack dùng mảng
12
@Nhận xét:
–
Các thao tác trên đều làm việc với chi phí O(1)
–
Việc cài đặt Stack thông qua mảng một chiều đơn giản
và khá hiệu quả
MÔN: CẤU TRÚC DỮ LIỆU
–
Tuy nhiên, hạn chế lớn nhất của phương án cài đặt này
là giới hạn về kích thước của Stack (N)
• Giá trị của N có thể quá nhỏ so với nhu cầu thực tế hoặc
quá lớn sẽ làm lãng phí bộ nhớ
• Nên hạn chế việc cài đặt ngăn xếp bằng mảng
6/12/14
/XX
12
- GV: NGUYỄN XUÂN VINH
Hiện thực Stack dùng DSLK
13 •
Có thể tạo một Stack bằng cách sử dụng một danh
sách liên kết đơn (DSLK)
•
Theo tính chất của dánh sách liên kết đơn phần
tử nằm ở đầu danh sách là dễ thêm và xóa nhất.
MÔN: CẤU TRÚC DỮ LIỆU
•
Do đó ta chọn:
–
Phần tử nằm ở đầu danh sách chính là đỉnh của
ngăn xếp.
–
Phần tử nằm ở cuối danh sách là đáy ngăn xếp.
6/12/14
/XX
13
- GV: NGUYỄN XUÂN VINH
Hiện thực Stack dùng DSLK
14
•
Khai báo ngăn xếp bằng danh sách liên kết:
–
Chỉ cần 1 biến để lưu phần tử đầu tiên trong
ngăn xếp (top).
Khởi tạo ngăn xếp rỗng:
MÔN: CẤU TRÚC DỮ LIỆU
•
–
Biến top được khởi tạo là null.
•
Kiểm tra ngăn xếp rỗng:
–
Ngăn xếp rỗng khi top là null.
•
Kiểm tra ngăn xếp đầy:
–
Ngăn xếp không có giới hạn về kích thước do
đó phương thức này không hỗ trợ.
6/12/14
/XX
14
- GV: NGUYỄN XUÂN VINH
Hiện thực Stack dùng DSLK
•
Thêm một phần tử vào ngăn xếp:
–
Tạo ra phần tử mới cho biến next của phần tử này trỏ tới top
hiện thời.
–
Top bây giờ sẽ là phần tử mới này.
Lấy một phần tử trong ngăn xếp:
MÔN: CẤU TRÚC DỮ LIỆU
•
–
Phần tử được lấy chính là top của ngăn xếp.
•
Xóa 1 phần tử khỏi ngăn xếp:
–
Top bây giờ là top.next.
6/12/14
/XX
15
- 16 /XX 6/12/14 MÔN: CẤU TRÚC DỮ LIỆU GV: NGUYỄN XUÂN VINH
Thêm một phần tử
- 17 /XX 6/12/14 MÔN: CẤU TRÚC DỮ LIỆU GV: NGUYỄN XUÂN VINH
Xóa một phần tử
- GV: NGUYỄN XUÂN VINH
Stack - Ứng dụng
18
•
Stack thích hợp lưu trữ các loại dữ liệu mà trình tự
truy xuất ngược với trình tự lưu trữ
•
Một số ứng dụng của Stack:
–
Trong trình biên dịch (thông dịch), khi thực hiện
MÔN: CẤU TRÚC DỮ LIỆU
các thủ tục, Stack được sử dụng để lưu môi
trường của các thủ tục
–
Lưu dữ liệu khi giải một số bài toán của lý
thuyết đồ thị (như tìm đường đi)
–
Khử đệ qui
–
Ứng dụng trong các bài toán tính toán biểu thức
6/12/14
–
…
/XX
18
- GV: NGUYỄN XUÂN VINH
Stack - Ứng dụng
19
Ví dụ: thủ tục Quick_Sort dùng Stack để khử đệ qui:
•
Bước 1. L=1; R=n;
•
Bước 2. Chọn phần tử giữa x=a[(L+R) / 2]
•
Bước 3. Phân hoạch (L, R) thành (L1, R1) và (L2, R2) bằng cách
xét:
MÔN: CẤU TRÚC DỮ LIỆU
–
y thuộc (L1, R1) nếu yx
–
y thuộc (L2, R2) ngược lại
•
Bước 4. Nếu phân hoạch (L2, R2) có nhiều hơn 1 phần tử thì thực
hiện:
–
Cất (L2, R2) vào Stack
–
Nếu (L1, R1) có nhiều hơn 1 phần tử thì thực hiện:
• L = L1
6/12/14
• R = R1
• Quay lên bước 2
/XX
–
Ngược lại
19
• Lấy (L, R) ra khỏi Stack, nếu Stack khác rỗng thì quay lên
- Stack Ứng dụng
GV: NGUYỄN XUÂN VINH
Bài tập: đổi số từ cơ số 10 sang cơ số x
MÔN: CẤU TRÚC DỮ LIỆU
57 2 Ví dụ: 57 = ???2
1 28 2 57 = 1110012
0 14 2
0 7 2
1 3 2
1 1 2
1 0
6/12/14
/XX
20
Thêm vào BST
Báo xấu
Download
Vui lòng tải xuống để xem tài liệu đầy đủ
