BÀI 14: DANH SÁCH TUYẾN TÍNH KIỂU HÀNG ĐỢI (QUEUE)
14.1. ĐỊNH NGHĨA
Hàng đợi là một vật chứa (container) các đối tượng làm việc theo cơ chế FIFO (First In
First Out) nghĩa là việc thêm một đối tượng vào hàng đợi hoặc lấy một đối tượng ra khỏi hàng đợi
được thực hiện theo cơ chế "Vào trước ra trước".
Các đối tượng có thể được thêm vào hàng đợi bất kỳ lúc nào nhưng chỉ có đối tượng thêm vào đầu
tiên mới được phép lấy ra khỏi hàng đợi.
Thao tác thêm một đối tượng vào hàng đợi và lấy một đối tượng ra khỏi hàng đợi lần lượt được gọi
là "enqueue" và "dequeue".
Việc thêm một đối tượng vào hàng đợi luôn diễn ra ở cuối hàng đợi và một phần tử luôn được lấy
ra từ đầu hàng đợi.
Ta hình dung nguyên tắc hoạt động của Queue như sau:
sn
s2 Queue
s1
Trong tin học, CTDL hàng đợi có nhiều ứng dụng: khử đệ qui, tổ chức lưu vết các quá trình tìm
kiếm theo chiều rộng và quay lui, vét cạn, tổ chức quản lý và phân phối tiến trình trong các hệ điều
hành, tổ chức bộ đệm bàn phím, .
Ta có thể định nghĩa CTDL hàng đợi như sau: hàng đợi là một CTDL trừu tượng (ADT) tuyến tính.
Tương tự như stack, hàng đợi hỗ trợ các thao tác:
EnQueue(o): Thêm đối tượng o vào cuối hàng đợi
DeQueue(): Lấy đối tượng ở đầu queue ra khỏi hàng đợi và trả về giá trị của nó. Nếu hàng đợi
rỗng thì lỗi sẽ xảy ra.
IsEmpty(): Kiểm tra xem hàng đợi có rỗng không.
Front(): Trả về giá trị của phần tử nằm ở đầu hàng đợi mà không hủy nó. Nếu hàng đợi rỗng
thì lỗi sẽ xảy ra.
Các thao tác thêm, trích và huỷ một phần tử phải được thực hiện ở 2 phía khác nhau của hàng đợi
do đó hoạt động của hàng đợi được thực hiện theo nguyên tắc FIFO (First In First Out - vào trước
ra trước).
Cũng như stack, ta có thể dùng cấu trúc mảng 1 chiều hoặc cấu trúc danh sách liên kết để biểu diễn
cấu trúc hàng đợi.

dựng thêm một thao tác phụ cho hàng đợi:
IsFull(): Kiểm tra xem hàng đợi có đầy chưa.
isEmpty(): Kiểm tra hàng đợi rỗng
bool IsFull() //Kiểm tra xem hàng đợi có đầy chưa.
{
return (count == N);
}
// Kiểm tra Queue rỗng nếu count =0;
bool isEmpty()
{
return count == 0;
}
void EnQueue(Data X) // Thêm một phần tử vào hàng đợi
{
if (IsFull() == false)
{
if (f == -1) // Hàng đợi rỗng
f =0;
if (r == N-1) r = 0;
else r ++;
Q[r] = X;
count ++; // Tăng số lượng phần tử có trong hàng đợi nên 1
}
}
Data DeQueue() // Lấy một phần tử ra khỏi Queue
{
if (isEmpty() == true) // Queue rỗng thì sinh ra một ngoại lệ
throw new Exception(“Hàng đợi rỗng”);
else {
Data x = Q[f];

x = RemoveFirst(ref Q);
return x;
}
• Xem thông tin của phần tử ở đầu hàng đợi
Data Front(LIST Q)
{
if (IsEmpty(Q)==1)
throw new Exception(“Hàng đợi rỗng”);
return Q.pHead.Info;
}
Các thao tác trên đều làm việc với chi phí O(1).
Chương trình minh họa hàng đợi có ưu tiên, cách cài đặt các nút trên hàng đợi có độ ưu tiên giảm
dần từ front tới rear.
pqinsert: Chèn nút mới vào vị trí thích hợp trên hàng đợi để đảm bảo độ ưu tiên của các nút giảm
dần từ front tới rear
pqremove: Xóa nút có độ ưu tiên cao nhất, nút này là nút tại front
using System;
namespace HangDoiUuTien
{
class pqueue
{
public static int MaxQueue = 100;
public int rear; // front luon la 0
public int[] Nodes = new int[MaxQueue]; // moi nut la mot so nguyen chi do uu tien
}
class Program
{
// Tac vu pqinitialize: khoi dong hang doi co uu tien
static void pqinitialize(pqueue ppq)
{

nay ta phai doi cac nut tu nut thu hai den nut cuoi xuong mot vi tri */
static int pqremove(ref pqueue ppq)
{
int x, i;
if (pqempty(ppq))
{
Console.WriteLine("Hang doi bi rong, khong xoa nut duoc");
throw new Exception("Hàng đợi rỗng");
}
else
{
x = ppq.Nodes[0]; // do uu tien cua nut can xoa
// doi cho
for (i = 0; i < ppq.rear; i++)
ppq.Nodes[i] = ppq.Nodes[i + 1];
ppq.rear--;
return x;
}
}
// Tac vu pqtraverse: duyet hang doi co uu tien tu front den rear
static void pqtraverse(pqueue ppq)
{
int i;
if (pqempty(ppq))
Console.WriteLine("hang doi bi rong");
else
for (i = 0; i <= ppq.rear; i++)
Console.WriteLine(ppq.Nodes[i]);
}
public static void Main(string[] args)

}
case 3:
{
Console.WriteLine("\nBan co chac khong (c/k): ");
string ch = Console.ReadLine();
if (ch == "c" || ch == "C")
pqinitialize(pq);
break;
}
case 4:
{
Console.WriteLine("\nDuyet hang doi: ");
pqtraverse(pq);
break;
}
}
} while (chucnang != 0);
}
}
}
Lưu ý, nếu không quản lý phần tử cuối xâu, thao tác dequeue sẽ có độ phức tạp O(n).
14.3 ỨNG DỤNG CỦA QUEUE
Hàng đợi có thể được sử dụng trong một số bài toán:
Bài toán sản xuất và tiêu thụ (ứng dụng trong các hệ điều hành song song).
Bộ đệm (ví dụ: Nhấn phím . Bộ đệm . CPU xử lý).
Xử lý các lệnh trong máy tính (ứng dụng trong HÐH, trình biên dịch), hàng đượi các tiến trình chờ
được xử lý, ..
Một số ví dụ:
Chương trình quản lý kho. Mặt hàng nào nhập kho trước sẽ được xuất kho trước.
// Chuong trinh viet bang con tro

pq.pTail = x;
}
}
static mathang remove(ref queue pq)
{
if(empty(pq))
throw new Exception("kho khong con hang");
else
{
mathang mh = pq.pHead;
pq.pHead = pq.pHead.next;
return mh;
}
}
// Tac vu traverse: duyet kho hang tu front toi rear
static void traverse( queue pq)
{
if(empty(pq))
{
Console.WriteLine("\nKho khong con hang");
return;
}
// vong lap in cac nut tu pHead den pTail
queue tmp = pq;
while(!(empty(tmp)))
{
Console.WriteLine(" "+ tmp.pHead.mamh+ " "+ tmp.pHead.tenmh );
tmp.pHead = tmp.pHead.next;
}
}

insert(ref q, mh);
break;
}
case 2:{
if(!empty(q))
{
mh = remove(ref q);
Console.WriteLine("\nMat hang xuat: Ma:"+ mh.mamh+ "Ten: "+ mh.tenmh);
}
else
Console.WriteLine("\nKho khong con hang");
break;
}
case 3:{
if (empty(q))
Console.WriteLine("Khong co hang trong kho");
else
Console.WriteLine("\nMat hang chuan bi xuat: Ma:"+ q.pHead.mamh + " Ten:" +
q.pHead.tenmh);
break;
}
case 4:{
Console.WriteLine("\nMat hang moi nhap: Ma:"+ q.pTail.mamh + " Ten:"+ q.pTail.tenmh);
break;
}
case 5:{
Console.WriteLine("\nCac mat hang co trong kho:");
Console.WriteLine( "MA MAT HANG", " TEN MAT HANG");
traverse(q);
break;