NGĂN XẾP & HÀNG ĐỢI-(Stack&Queue)

Chia sẻ: Vu Thi Thuy | Ngày: | Loại File: PDF | Số trang:9

Thêm vào BST

Báo xấu

89
lượt xem 24
download

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

Cấu trúc dữ liệu và giải thuật, Tài liệu tham khảo dành cho sinh viên năm 2 các trường chuyên ngành CNTT

Chủ đề:

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

Lưu

Nội dung Text: NGĂN XẾP & HÀNG ĐỢI-(Stack&Queue)

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 kt 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 kt 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