Hàng đợi (Queue) trong ngôn ngữ lập trình C/C++

Khác với ngăn xếp (Stack), Hàng đợi (Queue) là danh sách mà phép thêm vào được thực hiện ở đầu này còn phép loại bỏ được thực hiện ở đầu kia của danh sách. Như vậy phần tử thêm vào đầu tiên sẽ được lấy ra đầu tiên. Vậy hàng đợi được biểu diễn như thế nào? Các phép toán thao tác trên hàng đợi và ứng dụng của nó ra sao? Cùng Isinhvien tìm hiểu chi tiết qua bài viết dưới đây nhé!

Biễu diễn hàng đợi bằng danh sách liên kết

Xét hàng đợi các sinh viên gồm họ tên, chiều cao, cân nặng tiêu chuẩn.

Ta dùng danh sách liên kết để chứa các phần tử trong hàng đợi, một phần tử trong danh sách liên kết chứa một phần tử trong hàng đợi theo thứ tự là phần tử đầu tiên trong danh sách liên kết chứa phần tử đầu tiên trong hàng đợi.

typedef char infor1[15];
typedef float infor2;
typedef int infor3;
struct element
{ infor1 ht;
  infor2 cc;
  infor3 cntc;
  element *next;
};
typedef element *Queue;
Queue Front, Rear;

Trong đó:

• Biến con trỏ Front chỉ đến phần tử đầu tiên của danh sách liên kết, đó chính là phần tử đầu tiên của hàng đợi.
• Biến con trỏ Rear chỉ đến phần tử cuối cùng của danh sách liên kết, đó chính là phần tử cuối cùng của hàng đợi.

Các phép toán trên hàng đợi được biểu diễn bằng danh sách liên kết

Dưới đây là các phép toán thường được sử dụng trong hàng đợi.

1. Khởi tạo hàng đợi

Khi mới khởi tạo, hàng đợi là rỗng ta cho Front và Rear nhận giá trị NULL.

void Create(Queue &Front, Queue &Rear)
{ 
   Front=NULL; Rear=NULL;
}

2. Liệt kê các phần tử trong hàng đợi

Liệt kê lần lượt các phần tử trong hàng đợi, bắt đầu từ phần tử đầu tiên

void Display(Queue Front, Queue Rear)
{ 
   Queue p;
   p=Front;
   while (p != NULL)
   { 
     printf("\n %20s %7.2f %7d" , (p).ht , (p).cc , (p).cntc); 
     p=(p).next;
   }
}

3. Thêm một phần tử vào hàng đợi

Thêm một phần tử có họ tên x, chiều cao y và cân nặng z vào hàng đợi, phần tử sẽ thêm vào cuối danh sách liên kết

void InsertQueue(Queue &Front, Queue &Rear, infor1 x, infor2 y, infor3 z)
{ 
   Queue p;
   p=new element;
   strcpy((p).ht,x); (p).cc=y; (p).cntc=z; (p).next=NULL; 
   if (Front==NULL) Front=p;
   else (*Rear).next=p;
   Rear=p;
}

4. Xóa phần tử trong hàng đợi

Xóa phần tử đầu tiên khỏi hàng đợi.

void DeleteQueue(Queue &Front, Queue &Rear)
{ 
   Queue p;
   if (Front!=NULL)
   { 
     p=Front;
     Front=(*Front).next;
     if (Front==NULL) Rear=NULL;
     delete p;
   }
}

Ứng dụng của hàng đợi

Hàng đợi được sử dụng cho mọi tình huống mà bạn muốn duy trì hiệu quả thứ tự đầu tiên vào trước trên một số thực thể. Những tình huống này phát sinh theo nghĩa đen trong mọi loại phát triển phần mềm. 

Hãy tưởng tượng bạn có một trang web phục vụ các tệp cho hàng ngàn người dùng. Bạn không thể phục vụ tất cả các yêu cầu, bạn chỉ có thể xử lý 100 câu nói cùng một lúc. Một chính sách công bằng sẽ là phục vụ người đầu tiên đến trước: phục vụ 100 tại một thời điểm theo thứ tự đến. Một hàng đợi chắc chắn sẽ là cấu trúc dữ liệu phù hợp nhất.

Tương tự như vậy trong một hệ điều hành đa nhiệm, CPU không thể chạy tất cả các công việc cùng một lúc, do đó các công việc phải được sắp xếp lại và sau đó được lên lịch theo một số chính sách. Và hàng đợi sẽ là một lựa chọn vô cùng phù hợp trong trường hợp này.

Trên đây là tất tần tật những chia sẻ của Isinhvien về hàng đợi trong C/C++. Nếu cấc bạn thấy bài viết hay bổ ích thì hãy chia sẽ nó cho bạn bè cùng biết nhé, và đừng quên theo dõi Isinhvien để cập nhật thêm nhiều kiến thức hay mỗi ngày nhé! Chúc các bạn thật nhiều sức khỏe và gặt hái được nhiều thành công trong cuộc sống!