Bài giảng Cấu trúc dữ liệu và giải thuật chương 3: Ngăn xếp và hàng đợi

CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT Lý thuyết Phần 2 (Chương 3 – tiếp) Ngăn xếp và Hàng đợi „ Ngăn xếp „ Hàng đợi Vũ Anh Dũng - Khoa CNTT 2 Ngăn xếp ADT (Stack ADT) „ Ngăn xếp là một danh sách đặc biệt mà thao tác thêm (insert) và loại bỏ (delete) chỉ diễn ra ở 1 đầu. „ Ví trí tại đó phép thêm và xóa diễn ra luôn ở cuối của danh sách và được gọi là top. Vũ Anh Dũng - Khoa CNTT 3 Ngăn xếp ADT (Stack ADT) „ Mô hình ngăn xếp : „ Thêm 1 phần tử : push „ Loại bỏ 1 phần tử : pop Vũ Anh Dũng - Khoa CNTT 4 „ Kiểm tra và trả về giá trị của phần tử : top Ngăn xếp ADT (Stack ADT) „ Phép thêm và loại bỏ luôn diễn ra tại top Vũ Anh Dũng - Khoa CNTT 5 Cài đặt ngăn xếp „ Có thể sử dụng list hoặc vector „ Sử dụng list vector :, „ Thao tác push được thực hiện bằng việc hè à ối d h á hc n v o cu an s c „ Thao tác pop được thực hiện bằng cách ầ ốxóa ph n tử ở cu i danh sách „ Thao tác top chỉ đơn thuần kiểm tra phần Vũ Anh Dũng - Khoa CNTT 6 tử ở cuối danh sách, và trả về giá trị Cài đặt ngăn xếp „ Sử dụng list, vector : „ L push back(x);. _ „ L.pop_back(); „ int x= L.back(); Vũ Anh Dũng - Khoa CNTT 7 Cài đặt ngăn xếp „ Sử dụng mảng: „ Dùng thêm biến topOfStack để điều khiển các thao tác với ngăn xếp. topOfStack = 1 nếu ngăn xếp rỗng„ - . ầ ếYêu c u: Sinh viên tự vi t code cho cả 3 cài đặt sử dụng list, vector và array Vũ Anh Dũng - Khoa CNTT 8 Một số ứng dụng – Cân bằng ký hiệu (Balancing) „ Kiểm tra các dấu ngoặc trong quá trình kiểm tra lỗi cú pháp „ Tạo một ngăn xếp rỗng. „ Đọc các ký tự dấu Nế ký là ộ ký hiệ ở đặ ó à ă ế„ u tự m t u m , t n v o trong ng n x p. „ Nếu nó là một ký hiệu đóng, thì nếu ngăn xếp là rỗng thì thông báo một lỗi. Ngược lại, lấy ra khỏi ngăn xếp. ế ấ„ N u ký hiệu được l y ra không phải là ký hiệu mở tương ứng, thì thông báo một lỗi. „ Tại vị trí cuối của file, nếu ngăn xếp không rỗng thì thông báo một ỗ Vũ Anh Dũng - Khoa CNTT 9 l i. Một số ứng dụng – Biểu thức hậu tố (Postfix Exp) „ Xét biểu thức : 4 99 + 5 99 + 6 99* 1 06 =. . . . „ Nếu sử dụng máy tính thông thường để bấm thì kết ả là 19 05qu . „ Tuy nhiên, một số máy tính thông minh hơn ếsẽ chọn phép nhân ưu tiên trước và cho k t quả là 18.39 Vũ Anh Dũng - Khoa CNTT 10 Một số ứng dụng – Biểu thức hậu tố (Postfix Exp) „ Xét biểu thức : 4 99 * 1 06 + 5 99 + 6 99 * 1 06 =. . . . . „ Có thể sử dụng biểu thức Ba Lan dạng hậu tố hn ư sau : 4.99 1.06 * 5.99 + 6.99 1.06 * + Vũ Anh Dũng - Khoa CNTT 11 Một số ứng dụng – Biểu thức hậu tố (Postfix Exp) „ Ví dụ: „ 6 5 2 3 + 8 * + 3 + * „ Ban đầu : Vũ Anh Dũng - Khoa CNTT 12 Một số ứng dụng – Biểu thức hậu tố (Postfix Exp) „ Tiếp theo ‘+’ được đọc, do vậy 3 và 2 được lấy ra từ ngăn xếp và tổng của chúng, 5, được đNy vào. Vũ Anh Dũng - Khoa CNTT 13 Một số ứng dụng – Biểu thức hậu tố (Postfix Exp) „ Tiếp theo 8 được đNy vào „ Bây giờ ‘*’ được nhìn thấy, do vậy 8 và 5 ấ Nđược l y ra và 5 * 8 = 40 được đ y vào Vũ Anh Dũng - Khoa CNTT 14 Một số ứng dụng – Biểu thức hậu tố (Postfix Exp) „ Tiếp theo ‘+’ được nhìn thấy, do vậy 40 và 5 được lấy ra và 5 + 40 = 45 được đNy vào N„ 3 được đ y vào Vũ Anh Dũng - Khoa CNTT 15 Một số ứng dụng – Biểu thức hậu tố (Postfix Exp) „ ‘+’ tiếp theo lấy ra 3 và 45 và đNy vào 45 + 3 = 48 ố ấ„ Cu i cùng ‘*’ được nhìn th y và 48 và 6 được lấy ra; 6 * 48 = 288 được đNy vào Vũ Anh Dũng - Khoa CNTT 16 Một số ứng dụng – Chuyển từ trung tố sang hậu tố „ Sử dụng một ngăn xếp để chuyển một biểu thức ở dạng chuNn (được gọi theo cách khác là trung tố - infix) sang dạng hậu tố - postfix „ Chúng ta chỉ xét một bài toán nhỏ với các phép +, *, (, ) Ví dụ : a + b * c + ( d * e + f ) * g„ Được chuyển thành a b c * + d e * f + g * + Vũ Anh Dũng - Khoa CNTT 17 Một số ứng dụng – Chuyển từ trung tố sang hậu tố „ Một số quy tắc : „ Gặp toán hạng : chuyển qua đầu ra „ Gặp toán tử, hoặc dấu mở ngoặc : đưa vào stack „ Toán tử được đưa ra đầu ra sau khi xử lý, h dấ ặ hì khôn ưng u ngo c t ng „ Dấu + ưu tiên thấp nhất, ( là ưu tiên cao ấnh t Vũ Anh Dũng - Khoa CNTT 18 Một số ứng dụng – Chuyển từ trung tố sang hậu tố „ Đầu tiên, ký hiệu a được đọc, do vậy nó được truyền tới đầu ra. „ Sau đó + được đọc và được đặt lên trên ngăn xếp . „ Tiếp theo b được đọc và được truyền tới đầu ra. Vũ Anh Dũng - Khoa CNTT 19 Một số ứng dụng – Chuyển từ trung tố sang hậu tố „ Tiếp theo * được đọc. Mục ở đỉnh của ngăn xếp toán tử có quyền ưu tiên thấp hơn so với *, do vậy không có gì được đưa ra và * được đặt vào ngăn xếp. Tiếp theo, c được đọc và đưa ra output Vũ Anh Dũng - Khoa CNTT 20 Một số ứng dụng – Chuyển từ trung tố sang hậu tố „ Kí hiệu tiếp theo là +. Kiểm tra ngăn xếp, chúng ta thấy rằng chúng ta sẽ lấy ra * và đặt nó lên đầu ra; lấy ra + còn lại, nó có quyền ưu tiên không thấp hơn nhưng bằng, trên ngăn xếp; và sau đó đNy + vào stack. Vũ Anh Dũng - Khoa CNTT 21 Một số ứng dụng – Chuyển từ trung tố sang hậu tố „ Ký hiệu đọc tiếp theo là (, đang có quyền ưu tiên cao nhất, đặt nó lên trên ngăn xếp. Vũ Anh Dũng - Khoa CNTT 22 Một số ứng dụng – Chuyển từ trung tố sang hậu tố „ Bây giờ ta đọc ), do vậy ngăn xếp được làm rỗng cho tới ( Chúng ta đưa ra + . Vũ Anh Dũng - Khoa CNTT 23 Một số ứng dụng – Chuyển từ trung tố sang hậu tố C ối ù„ u c ng Vũ Anh Dũng - Khoa CNTT 24 Một số ứng dụng – Lời gọi hàm „ Các lời gọi hàm sử dụng ngăn xếp „ Có thể xem một ví dụ về gọi hàm đệ quy „ Hàm tính n! „ Hàm fibonaci Vũ Anh Dũng - Khoa CNTT 25 Hàng đợi ADT (Queue ADT) „ Hàng đợi là danh sách mà việc chèn được thực hiện ở một đầu trong khi việc xóa được thực hiện ở đầu còn lại „ Thêm phần tử : enqueue nó chèn một phần , tử vào cuối của danh sách (được gọi là rear) Xó hầ tử d ó ó ột hầ tử„ a p n : nqueue, n x a m p n ở đầu của danh sách (được gọi là front) Vũ Anh Dũng - Khoa CNTT 26 Mô hình hàng đợi „ Mô hình hàng đợi với phép enqueue và dequeue Vũ Anh Dũng - Khoa CNTT 27 Sử dụng mảng cài đặt hàng đợi „ Sử dụng mảng „ Mảng vòng tròn Vũ Anh Dũng - Khoa CNTT 28 Các ứng dụng của hàng đợi „ Điều phối công việc cho máy in „ Hàng đợi cuộc gọi „ Một số chương trình cần xử lý có hàng đợi í d h t ì h d đ á SMSv ụ : c ương r n ự o n qua Vũ Anh Dũng - Khoa CNTT 29