Bài giảng Cơ sở dữ liệu giải thuật: Bài 6 - Ngăn xếp

Bài 6: Ngăn x p<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 /> Ngăn x p<br /> • Ngăn x p là gì?<br /> – Là m t danh sách nhưng các phép toán ch<br /> m t nh c a danh sách.<br /> <br /> ư c th c hi n<br /> <br /> • Tính ch t<br /> – Vào trư c ra sau (First In Last Out: FILO)<br /> <br /> diepht@vnu<br /> <br /> 3<br /> <br /> KDLTT ngăn x p<br /> • Tr u tư ng hóa c u trúc ngăn x p<br /> –<br /> <br /> c t d li u<br /> A = (a0, a1, …, an)<br /> trong ó an là nh ngăn x p<br /> <br /> –<br /> 1.<br /> 2.<br /> 3.<br /> 4.<br /> 5.<br /> 6.<br /> <br /> diepht@vnu<br /> <br /> c t các phép toán<br /> Thêm ph n t x vào nh ngăn x p: push(x)<br /> Lo i ph n t<br /> nh ngăn x p: pop()<br /> Ki m tra ngăn x p có r ng hay không: isEmpty()<br /> Ki m tra ngăn x p có y hay không: isFull()<br /> m s ph n t c a ngăn x p: size()<br /> Tr v ph n t<br /> nh ngăn x p: top()<br /> <br /> 4<br /> <br /> Giao di n C++ c a KDLTT ngăn x p<br /> template <br /> class Stack {<br /> public:<br /> int size();<br /> bool isEmpty();<br /> Object& top()<br /> throw(EmptyStackException);<br /> void push(Object o);<br /> Object pop()<br /> throw(EmptyStackException);<br /> };<br /> <br /> diepht@vnu<br /> <br /> 5<br /> <br />