Bài giảng Cấu trúc dữ liệu và giải thuật - Bài 4: Hàng đợi và ngăn xếp

Hàng ñợi và Ngăn xếp (Queue and Stack) Lê Sỹ Vinh Bộ môn Khoa Học Máy Tính – Khoa CNTT ðại Học Công Nghệ - ðHQGHN Email: vinhioi@yahoo.com Hàng ñợi (Queue) Hàng ñợi là gì? Là một danh sách nhưng các phép toán chỉ ñược thực hiện ở hai ñỉnh của danh sách. Một ñỉnh gọi là ñầu hàng, ñỉnh còn lại gọi là cuối hàng. Ví dụ: • Xếp hàng mua vé tàu xe, giao dịch với ngân hàng Tính chất: Vào trước ra trước (First in First Out: FIFO) Hàng ñợi Trừu tượng hóa cấu trúc hàng ñợi 1. Mô tả dữ liệu A = (a0, a1, …, an) trong ñó: – ao: Phần tử ở ñầu của hàng ñợi A – an: Phần tử ở cuối của hàng ñợi A Ví dụ: A = (‘Vinh’, ‘Tuấn’,. ‘Ánh’) trong ñó: ‘Vinh’: ðầu hàng ñợi ‘Ánh’: Cuối hàng ñợi Các phép toán trên hàng ñợi • empty (A): Kiểm tra hàng ñợi có rỗng hay không • length (A): Cho biết số phần tử của hàng ñợi • EnQueue (A, x): Thêm phần tử x cuối hàng ñợi. A = (a0, a1,…, an) → A = (a0,a1,…,an , x) Ví dụ: A = (1,3,5) EnQueue (A, 4) → A = (1, 3, 5, 4) • DeQueue (A): Loại phần tử ở ñầu hàng ñợi A = (a0, a1,…, an-1, an) → A = (a1,…,an) Ví dụ: A = (1,3,5) DeQueue (A) → A = (3, 5) • GetHead (A): Lấy phần tử ở ñầu hàng ñợi A = (a0, a1,…, an-1, an) → getHead (A) → a0 Ví dụ: A = (1,3,5) getHead (A) → 1 Bài tập 1. Viết chương trình cài ñặt cấu trúc hàng ñợi bằng mảng và danh sách liên kết 2. Tính ñộ phức tạp cho cài ñặt ở câu 1 3. ðọc và cài ñặt hàng ñợi bằng màng tròn Ngăn xếp (stack) Ngăn xếp là gì? Là một danh sách nhưng các phép toán chỉ ñược thực hiện ở một ñỉnh của danh sách. Ví dụ: – Lấy hàng hóa trong kho – Tìm các cặp dấu ngoặc tương ứng Tính chất: Vào trước ra sau (First In Last Out: FILO) Ngăn xếp Trừu tượng hóa cấu trúc ngăn xếp 1. Mô tả dữ liệu A = (a0, a1, …, an) trong ñó an là phần tử ở ñỉnh của ngăn xếp A Ví dụ: A = (1, 2, 3, 3, 4, 5) → 5: Phần tử ở ñỉnh ngăn xếp A = (‘Vinh’, ‘Tuấn’,. ‘Ánh’) → Ánh: Phần tử ở ñỉnh ngăn xếp 2. Mô tả các phép toán trên cấu trúc ngăn xếp • empty (A): Kiểm tra ngăn xếp có rỗng hay không • length (A): Cho biết số phần tử của ngăn xếp Ngăn xếp (stack) • push (A, x): Thêm phần tử x ñỉnh ngăn xếp. A = (a0, a1,…, an) → A = (a0,a1,…,an , x) Ví dụ: A = (1,3,5) push (A, 4) → A = (1, 3, 5, 4) • Pop (A): Loại phần tử ở ñỉnh ngăn xếp A = (a0, a1,…, an-1, an) → A = (a0,a1,…,an-1) Ví dụ: A = (1,3,5) pop (A) → A = (1, 3) • GetTop (A): Lấy phần tử ở ñỉnh ngăn xếp A = (a0, a1,…, an-1, an) → getTop (A) → an Ví dụ: A = (1,3,5) getTop (A) → 5 Bài tập 1. Viết chương trình cài ñặt cấu trúc ngăn xếp bằng mảng và danh sách liên kết 2. Viết chương trình tìm tất cả các cặp dấu ngoặc tương ứng trong một chương trình C++ 3. Với mỗi phép toán, tính ñộ phức tạp