Bài giảng Cấu trúc dữ liệu: Hàng đợi - TS. Lê Minh Trung & Th.S Lương Trần Ngọc Khiết

Bài giảng Cấu trúc dữ liệu: Hàng đợi cung cấp cho người học những kiến thức như: Mô tả queue; Bus Stop Queue; Thiết kế của Queue; Cài đặt Queue sử dụng mảng; Thiết kế Queue dùng mảng; Array vòng với ngôn ngữ C++; Điều kiện biên của queue vòng; Phương thức Enqueue;... Mời các bạn cùng tham khảo!
Nội dung trích xuất từ tài liệu:
Bài giảng Cấu trúc dữ liệu: Hàng đợi - TS. Lê Minh Trung & Th.S Lương Trần Ngọc Khiết TS. Lê Minh Trung – ThS Lương Trần Ngọc KhiếtKhoa Công nghệ Thông tin, Đại học Sư phạm TP. HCMHàng đợi (Queue) Sử dụng mảng Sử dụng con trỏ Ứng dụng của hàng đợi Mô tả queue Một queue là một cấu trúc dữ liệu mà việc thêm vào được thực hiện ở một đầu (rear) và việc lấy ra được thực hiện ở đầu còn lại (front) Phần tử vào trước sẽ ra trước – FIFO (First In First Out)Bus Stop QueueBusStop front rear rear rear rear rear  Lấy 1 người ra khỏi QueueBus Stop QueueBusStop front rear rear rear Bus Stop QueueBusStop front rear rear Bus Stop QueueBusStop front rear rear  Thêm một người vào Queue.  Queue là một cấu trúc FIFO (First-In, First-Out). Thiết kế của Queuetemplateclass Queue{public:Queue(void); //phương thức khởi tạoQueue(const Queue &source); //phương thức khởi tạo~Queue(void); //phương thức hủybool IsEmpty() const; //kiểm tra queue rỗngbool IsFull() const; //kiểm tra queue đầyvoid Enqueue(NodeType &item); //thêm phần tử vào cuối queuevoid Dequeue(); //lấy phần tử ra khỏi đầu queueNodeType &Peek() const; //xem phần tử đầu queuevoid Clear(); //xóa sạch các phần tử trong queueint GetSize() const; //trả về kích cỡ của queue}; Cài đặt Queue sử dụng mảnghttp://www.cs.usfca.edu/~galles/visualization/QueueArray.html Thiết kế Queue dùng mảngconst int MAX =20;templateclass Queue{public: Queue(void); //phương thức khởi tạo ~Queue(void); //phương thức hủy bool IsEmpty() const;//kiểm tra rỗng bool IsFull() const;//kiểm tra đầy void Enqueue(const NodeType& item);//thêm phần tử vào cuối queue void Dequeue();//lấy phần tử ra từ đầu queue NodeType &Peek();//xem phần tử ở đầu queue void Clear();//xóa nội dung của queue int GetSize() const;//trả về kích cỡ của queueprivate: int front, rear; //đầu và cuối queue int count; //số phần tử của queue NodeType data[MAX];};Queue là array vòng (circular array)Array vòng với ngôn ngữ C++ Xem array như là một vòng:  phần tử cuối của array nối với phần tử đầu của array Tính toán vị trí kề:  i = ((i + 1) == MAX) ? 0 : (i + 1);  if ((i + 1) == MAX) i = 0; else i = i + 1;  i = (i + 1) % MAX;Điều kiện biên của queue vòng Các phương thứctemplate templateQueue::Queue(void) bool Queue::IsEmpty(){ const{ count=0; front =0; return count ==0; rear = MAX-1; }} templatetemplate bool Queue::IsFull() const{void Queue::Clear(){ return count ==MAX; count=0; front =0; } rear = MAX-1;for(int i=0; iThêm phần tử vào Queue Thêm một phần tử  Di chuyển ‘rear’ một đơn vị theo chiều kim đồng hồ.  Gán phần tử vào data[rear]. 16Phương thức Enqueuetemplatevoid Queue::Enqueue(const NodeType &item){ if(!IsFull()){ rear = (rear +1) % MAX; count ++; data[rear] = item; }else{ throw exception(Queue is full); }}Gỡ phần tử ra khỏi Queue Gỡ bỏ một phần tử  Di chuyển front một đơn vị theo chiều kim đồng hồ. 18Phương thức Dequeuetemplatevoid Queue::Dequeue(){ if(!IsEmpty()){ front = (front +1) % MAX; count --; }else{ throw exception(Queue is empty); }}templateNodeType &Queue::Peek(){ return data[front];}Thử nghiệm#include Queue.cpp#include Queue.h#include #include using namespace std;void main(){Queue queue;for(int i=1;i