Bài giảng Cấu trúc dữ liệu và giải thuật: Chương 8 - Trường ĐH Văn Lang

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!
Nội dung trích xuất từ tài liệu:
Bài giảng Cấu trúc dữ liệu và giải thuật: Chương 8 - Trường ĐH Văn Lang 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(S.count < N) // stack chưa đầy { S.D[count] = x; S.count++; } else puts('Stack đầy'); } 10 KHOA CÔNG NGHỆ THÔNG TIN public bool Push( int ivalue) { if (icount < iData.Length) // 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(S.count > 0) // stack khác rỗng { S.count--; x = S.D[count]; return x; } else puts('Stack rỗng') } 12 KHOA CÔNG NGHỆ THÔNG TIN public int Pop() { if (icount>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 int.MinValue; // 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 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. 14 KHOA CÔNG NGHỆ THÔNG TIN Kiểm tra stack rỗng hay không char IsEmpty(Stack S) { if(S.count == 0) // stack rỗng return 1; else return 0; } Kiểm tra stack đầy hay không char IsFull(Stack S) { if(S.count>= N) // stack đầy return 1; else return 0; } 15 KHOA CÔNG NGHỆ THÔNG TIN • Xem thông tin của phần tử ở đỉnh stack S Data Top() { Data x; if(count > 0) // stack khác rỗng { x = S.D[S.count-1]; return x; } else puts('Stack rỗng') } 16 KHOA CÔNG NGHỆ THÔNG TIN  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ả. • 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ớ. 17 KHOA CÔNG NGHỆ THÔNG TIN • Dùng danh sách liên kết đơn Head Đầu ds Class Node { ...