Hàng đợi và ngăn xếp

Chia sẻ: Le Quang Duan Duan | Ngày: | Loại File: PDF | Số trang:9

Thêm vào BST

Báo xấu

302
lượt xem 59
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Tài liệu tham khảo về hàng đợi và ngăn xếp - môn Khoa học máy tính

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: 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