Bài giảng Khoa học máy tính - Bài 4: Hàng đợi và ngăn xếp - Lê Sỹ Vinh

Nội dung text: Bài giảng Khoa học máy tính - Bài 4: Hàng đợi và ngăn xếp - Lê Sỹ Vinh

1. Hàng ủi và Ngăn xp (Queue and Stack) Lờ S Vinh B mụn Khoa Hc Mỏy Tớnh – Khoa CNTT ði Hc Cụng Ngh ðHQGHN Email: vinhioi@yahoo.com
2. Hàng ủi (Queue) Hàng ủi là gỡ? Là mt danh sỏch nhưng cỏc phộp toỏn ch ủưc thc hin hai ủnh ca danh sỏch. Mt ủnh gi là ủu hàng, ủnh cũn li gi là cui hàng. Vớ d: • Xp hàng mua vộ tàu xe, giao dch vi ngõn hàng Tớnh cht: Vào trưc ra trưc (First in First Out: FIFO)
3. Hàng ủi Tru tưng húa cu trỳc hàng ủi 1. Mụ t d liu A = ( a0, a 1, , a n) trong ủú: – ao: Phn t ủu ca hàng ủi A – an: Phn t cui ca hàng ủi A Vớ d: A = (‘Vinh’, ‘Tun’,. ‘Ánh’) trong ủú: ‘Vinh’: ðu hàng ủi ‘Ánh’: Cui hàng ủi
4. Cỏc phộp toỏn trờn hàng ủi • empty (A): Kim tra hàng ủi cú rng hay khụng • length (A): Cho bit s phn t ca hàng ủi • EnQueue (A, x ): Thờm phn t x cui hàng ủi. x A = (a 0, a 1, , a n) → A = (a 0,a 1, ,a n , ) Vớ d: A = (1,3,5) EnQueue ( A, 4) → A = (1, 3, 5, 4) • DeQueue (A): Loi phn t ủu hàng ủi A = (a 0, a 1, , a n1, a n) → A = (a 1, ,a n) Vớ d: A = (1,3,5) DeQueue ( A) → A = (3, 5) • GetHead (A): Ly phn t ủu hàng ủi A = (a 0, a 1, , a n1, a n) → getHead (A) → a 0 Vớ d: A = (1,3,5) getHead ( A) → 1
5. Bài t p 1. Vit chương trỡnh cài ủt cu trỳc hàng ủi bng mng và danh sỏch liờn kt 2. Tớnh ủ phc tp cho cài ủt cõu 1 3. ðc và cài ủt hàng ủi bng màng trũn
6. Ngăn xp (stack) Ngăn xp là gỡ? Là mt danh sỏch nhưng cỏc phộp toỏn ch ủưc thc hin mt ủnh ca danh sỏch. Vớ d: – Ly hàng húa trong kho – Tỡm cỏc cp du ngoc tương ng Tớnh cht: Vào trưc ra sau (First In Last Out: FILO)
7. Ngăn xp Tru tưng húa cu trỳc ngăn xp 1. Mụ t d liu A = ( a0, a 1, , a n) trong ủú an là phn t ủnh ca ngăn xp A Vớ d: A = (1, 2, 3, 3, 4, 5) → 5: Phn t ủnh ngăn xp A = (‘Vinh’, ‘Tun’,. ‘Ánh’) → Ánh: Phn t ủnh ngăn xp 2. Mụ t cỏc phộp toỏn trờn cu trỳc ngăn xp • empty (A): Kim tra ngăn xp cú rng hay khụng • length (A): Cho bit s phn t ca ngăn xp
8. Ngăn xp (stack) • push (A, x ): Thờm phn t x ủnh ngăn xp. x A = (a 0, a 1, , a n) → A = (a 0,a 1, ,a n , ) Vớ d: A = (1,3,5) push ( A, 4) → A = (1, 3, 5, 4) • Pop (A): Loi phn t ủnh ngăn xp A = (a 0, a 1, , a n1, a n) → A = (a 0,a 1, ,a n1) Vớ d: A = (1,3,5) pop ( A) → A = (1, 3) • GetTop (A): Ly phn t ủnh ngăn xp A = (a 0, a 1, , a n1, a n) → getTop (A) → a n Vớ d: A = (1,3,5) getTop ( A) → 5
9. Bài t p 1. Vit chương trỡnh cài ủt cu trỳc ngăn xp bng mng và danh sỏch liờn kt 2. Vit chương trỡnh tỡm tt c cỏc cp du ngoc tương ng trong mt chương trỡnh C++ 3. Vi mi phộp toỏn, tớnh ủ phc tp