Bài giảng Cấu trúc dữ liệu - Chương 7: Hàng đợi - Lê Minh Trung

TS. Lê Minh Trung – ThS Lương Trần Ngọc Khiết Khoa Công nghệ Thông tin, Đại học Sư phạm TP. HCM Hà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 Queue Bus Stop front rear rear rear rear rear  Lấy 1 người ra khỏi Queue Bus Stop Queue Bus Stop front rear rear rear Bus Stop Queue Bus Stop front rear rear Bus Stop Queue Bus Stop 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 Queue template class Queue { public: Queue(void); //phương thức khởi tạo Queue(const Queue &source); //phương thức khởi tạo ~Queue(void); //phương thức hủy bool IsEmpty() const; //kiểm tra queue rỗng bool IsFull() const; //kiểm tra queue đầy void Enqueue(NodeType &item); //thêm phần tử vào cuối queue void Dequeue(); //lấy phần tử ra khỏi đầu queue NodeType &Peek() const; //xem phần tử đầu queue void Clear(); //xóa sạch các phần tử trong queue int GetSize() const; //trả về kích cỡ của queue }; Cài đặt Queue sử dụng mảng  const int MAX =20; template class 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 queue private: int front, rear; //đầu và cuối queue int count; //số phần tử của queue NodeType data[MAX]; }; Thiết kế Queue dùng mảng 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ức template Queue::Queue(void) { count=0; front =0; rear = MAX-1; } template void Queue::Clear(){ count=0; front =0; rear = MAX-1; for(int i=0; i<MAX; i++) data[i]=0; } template bool Queue::IsEmpty() const{ return count ==0; } template bool Queue::IsFull() const{ return count ==MAX; } template int Queue::GetSize() const{ return count; } 16 Thê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]. Phương thức Enqueue template void Queue::Enqueue(const NodeType &item) { if(!IsFull()){ rear = (rear +1) % MAX; count ++; data[rear] = item; }else{ throw exception("Queue is full"); } } 18 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ồ. Phương thức Dequeue template void Queue::Dequeue(){ if(!IsEmpty()){ front = (front +1) % MAX; count --; }else{ throw exception("Queue is empty"); } } template NodeType &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<=10;i++)queue.Enqueue(i); while (!queue.IsEmpty()) { cout<<setw(4)<<queue.Peek()<<":"<<queue.GetSize(); queue.Dequeue(); } cout<<endl; } Cài đặt Queue sử dụng con trỏ  Thiết kế Node Node Cần: Dữ liệu Con trỏ để trỏ đến node sau Constructor Node Thiết kế Node template struct Node { NodeType item; // dữ liệu của Node Node *next; // con trỏ tới Node kế tiếp Node(); //phương thức khởi tạo Node(NodeType item, Node *ptr=nullptr); //phương thức khởi tạo }; Thiết kế Node #include "Node.h" template Node::Node(){} template Node::Node(NodeType item,Node *ptr=nullptr) { this->item= item; this->next = ptr; } Ví dụ với Node liên kết Node first_node(‘a’); Node *p0 = &first_node; Node *p1 = new Node(‘b’); p0->next = p1; Node *p2 = new Node(‘c’, p0); p1->next = p2; a first_node p0 b p1 c p2 Queue liên kết  Thiết kế:  Dùng hai con trỏ chỉ đến đầu và cuối của danh sách dữ liệu (front và rear)  Khởi tạo rỗng: gán cả front và rear về NULL front middle last front rear front rear Thiết kế Queue template class Queue { public: Queue(void); Queue(const Queue &source); ~Queue(void); bool IsEmpty() const; void Enqueue(const NodeType &item); void Dequeue(); NodeType &Peek() const; void operator=(const Queue &source); void Clear(); private: Node *front; Node *rear; void Copy(const Queue &source, Node* & destFront, Node* & destRear)); }; Thêm phần tử vào một queue liên kết  Giải thuật: 1. Tạo một node mới với dữ liệu cần thêm vào 2. Nếu queue đang rỗng 2.1. front và rear là node mới 3. Ngược lại 3.1. Nối node mới vào sau rear 3.2. rear chính là node mới rear front middle last front new_last new_rear Phương thức Enqueue template void Queue::Enqueue(const NodeType &item) { Node *newNode = new Node(item); //tạo node mới if(newNode != nullptr){ if(front==nullptr){front=rear= newNode; }//Queue đang rỗng else{ rear -> next = newNode; rear = newNode; } }else { throw exception("Not enough memory"); } } Bỏ phần tử khỏi một queue liên kết  Giải thuật: 1. Dùng một con trỏ để giữ lại front hiện tại 2. Nếu queue có một phần tử 2.1. Gán front và rear về NULL 3. Ngược lại 3.1. Trỏ front đến nút kế sau 4. Xóa nút cũ đi old_front front front middle last rear Phương thức Dequeue template void Queue::Dequeue() { if(front !=nullptr){ //queue không rỗng Node *oldFront = front; front=oldFront->next; if(front==nullptr)rear = nullptr; delete oldFront; }else{ throw exception("Queue is emty"); } } Sự không an toàn con trỏ trong C++  Kết thúc biến queue nhưng bộ nhớ còn lại:  delete queue0;  Gán hai queue: cả hai dùng chung một vùng dữ liệu  queue2 = queue1; top middle last top middle last queue0 queue1 queue2 top middle last Đảm bảo an toàn con trỏ trong C++  Destructor (phương thức hủy):  Sẽ được gọi ngay trước khi đối tượng kết thúc thời gian sống  Dùng xóa hết vùng dữ liệu  Copy constructor:  Sẽ được gọi khi khởi tạo biến lúc khai báo, hoặc truyền dữ liệu bằng tham trị  Sao chép nguồn thành một vùng dữ liệu mới  Assignment operator (toán tử gán):  Sẽ được gọi khi gán đối tượng này vào đối tượng khác  Xóa vùng dữ liệu của đích và đồng thời sao chép nguồn thành một vùng dữ liệu mới Hủy vùng nhớ đã được cấp cho Queue template void Queue::Clear(){ while (!IsEmpty()) { Dequeue(); } } template Queue::~Queue(void) { Clear(); } Sao chép vùng dữ liệu – Ví dụ a b c copy_node new_top new_copy a b c copy.top_node Sao chép vùng dữ liệu template void Queue::Copy(const Queue &source, Node* & destFront, Node * & destRear){ Node *curS, *curD; curS= source.front; if(curS == nullptr)return; //queue rỗng destFront = curD = new Node(curS -> item); while(curS -> next != nullptr){//vẫn còn phần tử cần duyệt curS = curS -> next; curD -> next = new Node(curS ->item); curD = curD -> next; } destRear = curD; } Copy constructor và toán tử gán template Queue::Queue(const Queue &source) { Copy(source, front, rear); } template void Queue::operator=(const Queue &source) { Clear(); Copy(source, front, rear); } Phương thức khác template bool Queue::IsEmpty() const { return front==nullptr; } template NodeType &Queue::Peek() const { return front -> item; } Thử nghiệm #include "Queue.cpp" #include "Node.cpp" #include #include #include using namespace std; void main(){ Queue q; q.Enqueue("I"); q.Enqueue("love !"); q.Enqueue("you"); while(!q.IsEmpty()){ cout << q.Peek() << " "; q.Dequeue(); } cout << endl; } Ứng dụng của Queue  Sử dụng trong nhiều bài toán, thuật toán  Thuật toán điều phối CPU của hệ điều hành  Biểu diễn các đa thức, tính toán đa thức Ứng dụng: tính toán đa thức  Thiết kế cấu trúc dữ liệu cho đa thức:  Một bản ghi có thành phần mũ và hệ số  Một danh sách các bản ghi theo thứ tự giảm của số mũ  Có thể dùng queue Giải thuật cộng hai đa thức 1 Algorithm Equals_sum1 Input: p,q là hai đa thức Output: đa thức tổng 1. Trong khi p và q chưa rỗng 1.1. Lấy phần tử front của p và q thành p_term, q_term 1.2. Nếu bậc của p_term lớn (hoặc nhỏ) hơn bậc của q_term 1.2.1. Đẩy p_term (hoặc q_term) vào kết quả 1.2.2. Bỏ phần tử đầu trong p (hoăc trong q) 1.3. Ngược lại 1.3.1. Tính hệ số mới cho số hạng này 1.3.2. Đẩy vào kết quả 2. Nếu p (hoặc q) chưa rỗng 2.1. Đẩy toàn bộ p (hoặc q) vào kết quả End Equals_sum1 Ví dụ cộng hai đa thức bằng giải thuật 1 p = 3x6 – 2x4 + x3 + 4 q = 5x5 + 2x4 + 4x2 + 2x p + q = 3x6 + 5x5 + x3 + 4x2 + 2x + 4 Giải thuật cộng hai đa thức 2 Algorithm Bac_da_thuc Input: đa thức Output: bậc của đa thức 1. Nếu đa thức rỗng 1.1. Trả về -1 2. Trả về bậc của phần tử đầu End Bac_da_thuc Algorithm Equals_sum2 Input: p,q là hai đa thức Output: đa thức tổng 1. Trong khi p hoặc q chưa rỗng 1.1. Nếu bậc của p lớn hơn bậc của q 1.1.1. Lấy từ p thành term 1.1.2. Đẩy term vào kết quả 1.2. Nếu bậc của q lớn hơn bậc của p 1.2.1. Lấy từ q thành term 1.2.2. Đẩy term vào kết quả 1.3. Ngược lại 1.3.1. Lấy p_term, q_term từ p và q 1.3.2. Tính tổng hai hệ số 1.3.3. Nếu hệ số kết quả khác không 1.3.3.1. Đẩy vào kết quả End Equals_sum2 Ví dụ cộng hai đa thức bằng giải thuật 2 degree(p) = degree(p) = 5 6 p = 3x6 – 2x4 + x3 + 4 q = 5x5 + 2x4 + 4x2 + 2x p + q = 3x6 + 5x5 + x3 + 4x2 + 2x + 4 4 4 3 2 0 1-1 -1 CÁM ƠN VÌ ĐÃ LẮNG NGHE!