Bài giảng Cơ sở dữ liệu giải thuật: Bài 6 - Hàng đợi

Bài 7: Hàng<br /> <br /> i<br /> <br /> Gi ng viên: Hoàng Th i p<br /> Khoa Công ngh Thông tin –<br /> i h c Công Ngh<br /> <br /> Ngu n tham kh o chính:<br /> http://www.cs.nyu.edu/~melamed/courses/102/lectures/<br /> http://users.encs.concordia.ca/~dssouli/COEN352.html<br /> <br /> T ng quan<br /> <br /> diepht@vnu<br /> <br /> 2<br /> <br /> Hàng<br /> • Hàng<br /> <br /> i<br /> <br /> i là gì?<br /> <br /> – Là m t danh sách nhưng các phép toán ch ư c th c hi n hai nh<br /> 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.<br /> <br /> • Tính ch t<br /> – Vào trư c ra trư c (First In First Out: FIFO)<br /> <br /> diepht@vnu<br /> <br /> 3<br /> <br /> KDLTT hàng<br /> • Tr u tư ng hóa c u trúc hàng<br /> –<br /> <br /> i<br /> i<br /> <br /> c t d li u<br /> A = (a0, a1, …, an)<br /> trong ó a0 là u hàng<br /> <br /> –<br /> 1.<br /> 2.<br /> 3.<br /> 4.<br /> 5.<br /> 6.<br /> <br /> diepht@vnu<br /> <br /> i, an là cu i hàng<br /> <br /> i<br /> <br /> c t các phép toán<br /> Thêm ph n t x vào cu i hàng i: enqueue(x)<br /> Lo i ph n t<br /> u hàng i: dequeue()<br /> Ki m tra hàng i có r ng hay không: isEmpty()<br /> Ki m tra hàng i h t ch hay chưa: isFull()<br /> m s ph n t c a hàng i: size()<br /> Tr v ph n t<br /> u hàng i: front()<br /> <br /> 4<br /> <br /> Giao di n C++ c a KDLTT hàng<br /> <br /> i<br /> <br /> template <br /> class Queue {<br /> public:<br /> int size();<br /> bool isEmpty();<br /> Object& front()<br /> throw(EmptyQueueException);<br /> void enqueue(Object o);<br /> Object dequeue()<br /> throw(EmptyQueueException);<br /> };<br /> <br /> diepht@vnu<br /> <br /> 5<br /> <br />