Bài giảng Cấu trúc dữ liệu và giải thuật: Chương 8 cung cấp cho người học những kiến thức như: Ngăn xếp; hàng đợi; bài tập stack và queue. Mời các bạn cùng tham khảo! | 3 KHOA CÔNG NGHỆ THÔNG TIN 4 KHOA CÔNG NGHỆ THÔNG TIN Cơ chế Last In First Out LIFO Stack 5 KHOA CÔNG NGHỆ THÔNG TIN Mảng 1 chiều Danh sách liên kết đơn Cấp phát Kích thước stack động khi quá thiếu lúc quá thừa Push Pop Push Pop hơi khá dễ dàng phức tạp 6 KHOA CÔNG NGHỆ THÔNG TIN Để khai báo một stack ta cần một mảng 1 chiều S biến nguyên t cho biết chỉ số của đầu stack và hằng số N cho biết kích thước tối đa của struct Stack Data D N int count 7 KHOA CÔNG NGHỆ THÔNG TIN Lệnh count 0 sẽ tạo ra một stack S rỗng. Giá trị của count sẽ cho biết số phần tử hiện hành có trong stack Khi cài đặt bằng mảng 1 chiều stack có kích thước tối đa nên cần xây dựng thêm một thao tác phụ cho stack IsFull Kiểm tra xem stack có đầy chưa. Khi stack đầy việc gọi đến hàm push sẽ phát sinh ra lỗi. overflow error 8 KHOA CÔNG NGHỆ THÔNG TIN class StackByArray int iData lưu dữ liệu của stack int icount số phần tử stack đang lưu trữ public StackByArray int size iData new int size icount 0 9 KHOA CÔNG NGHỆ THÔNG TIN Thêm một phần tử x vào stack S void Push Stack S Data x if lt N stack chưa đầy count x else puts quot Stack đầy quot 10 KHOA CÔNG NGHỆ THÔNG TIN public bool Push int ivalue if icount lt stack chưa đầy iData icount ivalue bỏ giá trị vào stack icount tăng số phần tử trong stack return true thêm phần tử thành công else stack đầy overflow error return false thêm phần tử thất bại 11 KHOA CÔNG NGHỆ THÔNG TIN Trích thông tin và huỷ phần tử ở đỉnh stack S Data Pop Stack S Data x if gt 0 stack khác rỗng x count return x else puts quot Stack rỗng quot 12 KHOA CÔNG NGHỆ THÔNG TIN public int Pop if icount gt 0 icount- giảm số lượng phần tử trong stack return iData icount 1 trả giá trị đỉnh stack về else stack không có phần tử underflow error return trả min số nguyên về để biết mảng không có phần tử 13 KHOA CÔNG NGHỆ THÔNG TIN Lệnh count 0 sẽ tạo ra một stack S rỗng. Giá trị của count sẽ cho biết số phần tử hiện hành có trong .
