Bài giảng "Cấu trúc dữ liệu và giải thuật - Bài 6: Ngăn xếp" cung cấp cho người học các kiến thức: Tổng quan quan, ngăn xếp, giao diện C++ của KDLTT ngăn xếp, ngăn xếp chạy chương trình của C++,. nội dung chi tiết. | HK I, 2012-2013 Bài 7: Hàng đợi Giảng viên: Hoàng Thị Điệp Khoa Công nghệ Thông tin – Đại học Công Nghệ Nguồn tham khảo chính: Tổng quan Cấu trúc dữ liệu Không tuyến tính Tuyến tính Truy cập ngẫu nhiên/trực tiếp diepht@vnu Truy cập tuần tự Tập hợp (Set) Thành phần đồng nhất Thành phần không đồng nhất Tổng quát Vào-trước-ratrước Vào-sau-ratrước Mảng (Array) Bản ghi (Record) Danh sách liên kết (List) Hàng đợi (Queue) Ngăn xếp (Stack) INT2203/w07 2 Hàng đợi • 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. • Tính chất – Vào trước ra trước (First In First Out: FIFO) diepht@vnu INT2203/w07 3 KDLTT hàng đợi • Trừu tượng hóa cấu trúc hàng đợi Đặc tả dữ liệu – A = (a0, a1, , an) trong đó a0 là đầu hàng đợi, an là cuối hàng đợi – Đặc tả các phép toán 1. Thêm phần tử x vào cuối hàng đợi: enqueue(x) 2. Loại phần tử ở đầu hàng đợi: dequeue() 3. Kiểm tra hàng đợi có rỗng hay không: isEmpty() 4. Kiểm tra hàng đợi hết chỗ hay chưa: isFull() 5. Đếm số phần tử của hàng đợi: size() 6. Trả về phần tử ở đầu hàng đợi: front() diepht@vnu INT2203/w07 4 Giao diện C++ của KDLTT hàng đợi template class Queue { public: int size(); bool isEmpty(); Object& front() throw(EmptyQueueException); void enqueue(Object o); Object .
