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 (Queue and Stack)- Lê Sỹ Vinh

Nội dung text: 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 (Queue and Stack)- 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