Khoa học máy tính - Hàng đợi và ngăn xếp

Chia sẻ: Nguyen Van Dai | Ngày: | Loại File: PDF | Số trang:9

Thêm vào BST

Báo xấu

209
lượt xem 42
download

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

Hàng đợi (tiếng Anh: queue) là một cấu trúc dữ liệu dùng để chứa các đối tượng làm việc theo cơ chế FIFO (viết tắt từ tiếng Anh: First In First Out), nghĩa là "vào trước ra trước. Trong hàng đợi, các đối tượng có thể được thêm vào hàng đợi bất kỳ lúc nào, nhưng chỉ có đối tượng thêm vào đầu tiên mới được phép lấy ra khỏi hàng đợi. Thao tác thêm vào và lấy một đối tượng ra khỏi hàng đợi được gọi lần lượt là "enqueue" và "dequeue". Việc thêm một đối tượng luôn diễn...

Chủ đề:

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

Lưu

Nội dung Text: Khoa học máy tính - 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 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