Giáo trình Cấu trúc dữ liệu và giải thuật - Chương 3: Hàng đợi

ến tính có front luôn chỉ vị trí đầu tiên trong 
hàng và mọi phần tử của hàng phải di chuyển tới một bước khi phần tử tại 
front được lấy đi. Đây là phương pháp rất dở trong máy tính nói chung. 
• Một dãy tuyến tính có hai chỉ số front và rear luôn luôn tăng. Đây là 
phương pháp tốt nếu như hàng có thể được làm rỗng. 
• Một dãy vòng có hai chỉ số front,rear và một vị trí để trống. 
• Một dãy vòng có hai chỉ số front,rear và một cờ cho biết hàng đầy (hoặc 
rỗng). 
• Một dãy vòng có hai chỉ số front,rear và một biến đếm số phần tử hiện có 
trong hàng. 
• Một dãy vòng có hai chỉ số front,rear mà hai chỉ số này sẽ mang trị đặc 
biệt trong trường hợp hàng rỗng. 
3.3.2. Phương án hiện thực hàng liên kết 
Bằng cách sử dụng bộ nhớ liên tục, việc hiệc thực hàng khó hơn việc hiện thực 
ngăn xếp rất nhiều do chúng ta dùng vùng nhớ tuyến tính để giả lặp tổ chức vòng 
và gặp khó khăn trong việc phân biệt một hàng đầy với một hàng rỗng. Tuy 
nhiên, hiện thực hàng liên kết lại thực sự dễ dàng như hiện thực ngăn xếp liên 
kết. Chúng ta chỉ cần nắm giữ hai con trỏ, front và rear để tham chiếu đến 
phần tử đầu và phần tử cuối của hàng. Các tác vụ thêm hay loại phần tử trên 
hàng được minh họa trong hình 3.5. 
Chương 3 – Hàng đợi 
Giáo trình Câu trúc dữ liệu và Giải thuật 46
3.4. Hiện thực hàng 
3.4.1. Hiện thực hàng liên tục 
Hiện thực vòng cho hàng liên tục trong C++ 
Phần này trình bày các phương thức của cách hiện thực hàng bằng dãy vòng 
có biến đếm các phần tử. Chúng ta có định nghĩa lớp Queue như sau: 
const int maxQueue = 10; // Giá trị nhỏ chỉ để kiểm tra CTDL Queue. 
template 
class Queue { 
public: 
 Queue(); 
 bool empty() const; 
 ErrorCode serve(); 
 ErrorCode append(const Entry &item); 
 ErrorCode retrieve(Entry &item) const; 
protected: 
 int count; 
 int front, rear; 
 Entry entry[maxQueue]; 
}; 
Các dữ liệu thành phần trong lớp Queue được khai báo protected. Đối với người sử dụng sẽ 
không có gì thay đổi, nghĩa là chúng vẫn không được người sử dụng nhìn thấy và vẫn đảm bảo sự 
che dấu thông tin. Mục đích ở đây là khi chúng ta xây dựng lớp Extended_Queue dẫn xuất từ lớp 
Queue thì lớp dẫn xuất sẽ sử dụng được các dữ liệu thành phần này. Khi các dữ liệu thành phần 
của lớp cơ sở được khai báo là private thì lớp dẫn xuất cũng sẽ không nhìn thấy chúng. 
template 
Queue::Queue() 
/* 
post: đối tượng hàng đã tồn tại và được khởi tạo là hàng rỗng. 
*/ 
Hình 3.5 Các tác vụ thêm và loại phần tử trên hàng liên kết 
Chương 3 – Hàng đợi 
Giáo trình Câu trúc dữ liệu và Giải thuật 47
{ 
 count = 0; 
 rear = maxQueue - 1; 
 front = 0; 
} 
template 
bool Queue::empty() const 
/* 
post: hàm trả về true nếu hàng rỗng; ngược lại, hàm trả về false. 
*/ 
{ return count == 0; 
} 
template 
ErrorCode Queue::append(const Entry &item) 
/* 
post: nếu hàng còn chỗ, item được thêm vào tại rear, ErrorCode trả về là success; ngược lại, 
ErrorCode trả về là overflow, hàng không đổi. 
*/ 
{ 
 if (count >= maxQueue) return overflow; 
 count++; 
 rear = ((rear + 1) == maxQueue) ? 0 : (rear + 1); 
 entry[rear] = item; 
 return success; 
} 
template 
ErrorCode Queue::serve() 
/* 
post: nếu hàng không rỗng, phần tử tại front được lấy đi, ErrorCode trả về là success; ngược 
lại, ErrorCode trả về là underflow, hàng không đổi. 
*/ 
{ 
 if (count <= 0) return underflow; 
 count--; 
 front = ((front + 1) == maxQueue) ? 0 : (front + 1); 
 return success; 
} 
template 
ErrorCode Queue::retrieve(Entry &item) const 
/* 
post: nếu hàng không rỗng, phần tử tại front được chép vào item, ErrorCode trả về là 
success; ngược lại, ErrorCode trả về là underflow; cả hai trường hợp hàng đều không 
đổi. 
*/ 
{ 
 if (count <= 0) return underflow; 
 item = entry[front]; 
 return success; 
} 
Chúng ta dành phương thức empty lại như là bài tập. Phương thức size dưới 
đây rất đơn giản do lớp Extended_Queue sử dụng được thuộc tính count của lớp 
Chương 3 – Hàng đợi 
Giáo trình Câu trúc dữ liệu và Giải thuật 48
Queue, nếu như count được khai báo là private thì phương thức size của lớp 
Extended_Queue phải sử dụng hàng loạt câu lệnh gọi các phương thức public 
của Queue như serve, retrieve, append mới thực hiện được. Các phương thức 
còn lại của Extended_Queue cũng tương tự, và chúng ta dành lại phần bài tập. 
template 
int Extended_Queue::size() const 
/* 
post: trả về số phần tử hiện có của hàng. Hàng không đổi. 
*/ 
{ 
 return count; 
} 
3.4.2. Hiện thực hàng liên kết 
3.4.2.1. Các khai báo cơ bản 
Với mọi hàng, chúng ta dùng kiểu Entry cho kiểu của dữ liệu lưu trong hàng. 
Đối với hiện thực liên kết, chúng ta khai báo các node tương tự như đã làm cho 
ngăn xếp liên kết trong chương 2. Chúng ta có đặc tả dưới đây: 
template 
class Queue { 
public: 
// Các phương thức chuẩn của hàng 
 Queue(); 
 bool empty() const; 
 ErrorCode append(const Entry &item); 
 ErrorCode serve(); 
 ErrorCode retrieve(Entry &item) const; 
// Các phương thức bảo đảm tính an toàn cho hàng liên kết 
 ~Queue(); 
 Queue(const Queue &original); 
 void operator =(const Queue &original); 
protected: 
 Node *front, *rear; 
}; 
Constructor thứ nhất khởi tạo một hàng rỗng: 
template 
Queue::Queue() 
/* 
post: đối tượng hàng đã tồn tại và được khởi tạo là hàng rỗng. 
*/ 
{ 
 front = rear = NULL; 
} 
Chương 3 – Hàng đợi 
Giáo trình Câu trúc dữ liệu và Giải thuật 49
Phương thức append thêm một phần tử vào đầu rear của hàng: 
template 
ErrorCode Queue::append(const Entry &item) 
/* 
post: nếu hàng còn chỗ, item được thêm vào tại rear, ErrorCode trả về là success; ngược 
lại, ErrorCode trả về là overflow, hàng không đổi. 
*/ 
{ 
 Node *new_rear = new Node (item); 
 if (new_rear == NULL) return overflow; 
 if (rear == NULL) front = rear = new_rear; // trường hợp đặc biệt: thêm vào hàng 
đang rỗng. 
 else { 
 rear->next = new_rear; 
 rear = new_rear; 
 } 
 return success; 
} 
Trường hợp hàng rỗng cần phân biệt với các trường hợp bình thường khác, do 
khi thêm một node vào một hàng rỗng cần phải gán cả front và rear tham 
chiếu đến node này, trong khi việc thêm một node vào một hàng không rỗng chỉ 
có rear là cần được gán lại. 
Phương thức loại một phần tử ra khỏi hàng được viết như sau: 
template 
ErrorCode Queue::serve() 
/* 
post: nếu hàng không rỗng, phần tử tại front được lấy đi, ErrorCode trả về là success; ngược 
lại, ErrorCode trả về là underflow, hàng không đổi. 
*/ 
{ 
 if (front == NULL) return underflow; 
 Node *old_front = front; 
 front = old_front->next; 
 if (front == NULL) rear= NULL;// trường hợp đặc biệt: loại phần tử cuối cùng của hàng 
 delete old_front; 
 return success; 
} 
Một lần nữa trường hợp hàng rỗng cần được xem xét riêng. Khi phần tử được 
loại khỏi hàng không phải là phần tử cuối trong hàng, chỉ có front cần được gán 
lại, ngược lại cả front và rear cần phải gán về NULL. 
Các phương thức khác của hàng liên kết được dành lại cho phần bài tập. 
Chương 3 – Hàng đợi 
Giáo trình Câu trúc dữ liệu và Giải thuật 50
Nếu so sánh với hàng liên tục, chúng ta sẽ thấy rằng hàng liên kết dễ hiểu 
hơn cả về mặt khái niệm cả về cách hiện thực chương trình. 
3.4.3. Hàng liên kết mở rộng 
Hiện thực liên kết của lớp Queue cung cấp một lớp cơ sở cho các lớp khác. 
Định nghĩa dưới đây dành cho lớp dẫn xuất Extended_Queue hoàn toàn tương tự 
như hàng liên tục. 
template 
class Extended_queue: public Queue { 
public: 
 bool full() const; 
 int size() const; 
 void clear(); 
 ErrorCode serve_and_retrieve(Entry &item); 
}; 
Mặc dù lớp Extended_Queue này có hiện thực liên kết, nhưng nó không cần các phương thức 
như copy contructor, overloaded assignment, hoặc destructor. Đối với một trong các phương thức 
này, trình biên dịch sẽ gọi các phương thức mặc định của lớp Extended_Queue. Phương thức mặc 
định của một lớp dẫn xuất sẽ gọi phương thức tương ứng của lớp cơ sở. Chẳng hạn, khi một đối 
tượng của lớp Extended_Queue chuẩn bị ra khỏi tầm vực, destructor mặc định của lớp 
Extended_Queue sẽ gọi destructor của lớp Queue: mọi node cấp phát động của Extended_Queue 
đều được giải phóng. Do lớp Extended_Queue của chúng ta không chứa thêm thuộc tính con trỏ 
nào ngoài các thuộc tính con trỏ thừa kế từ lớp Queue, destructor mà trình biên dịch gọi đã làm 
được tất cả những điều mà chúng ta mong muốn. 
Các phương thức được khai báo cho lớp Extended_Queue cần được viết lại cho 
phù hợp với cấu trúc liên kết của hàng. Chẳng hạn, phương thức size cần sử dụng 
một con trỏ tạm window để duyệt hàng (nói cách khác, con trỏ window sẽ di 
chuyển dọc theo hàng và lần lượt chỉ đến từng node trong hàng). 
template 
int Extended_queue::size() const 
/* 
post: trả về số phần tử hiện có của hàng. Hàng không đổi. 
*/ 
{ 
 Node *window = front; 
 int count = 0; 
 while (window != NULL) { 
 window = window->next; 
 count++; 
 } 
 return count; 
} 
Các phương thức khác của Extended_Queue liên kết xem như bài tập.