Bài giảng Hàng đợi và ngăn xếp (Queue and Stack)

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