Cấu Trúc Dữ Liệu Trong Java Bài 3: Hàng Đợi (Queue) Và Các Thao Tác Cơ Bản Trên Hàng Đợi

Hàng đợi (Queue) là một cấu trúc dữ liệu dùng để chứa các đối tượng làm việc theo cơ chế FIFO (viết tắt từ tiếng Anh: First In First Out), nghĩa là “vào trước ra trước” Trong hàng đợi, 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. Việc thêm một đối tượng 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.

1. Queue cài đặt trên mảng

1 2 3 4 5 6 7 8 9

#define Max 5 //so phan tu toi da cua Queue typedef int item; //kieu du lieu class Queue {     int Front, Rear; //front: phan tu dau hang, rear: phan tu cuoi hang     item Data[Max]; //Mang cac phan tu     int count; //dem so phan tu cua Queue };

1.1 Khởi tạo Queue rỗng.

Để khởi tạo Queue rỗng ta cần đưa vị trí Front về 0, Rear về -1, cout về 0.

1 2 3 4 5 6

void Init (Queue Q) //khoi tao Queue rong {     Q.Front = 0; //phan tu dau     Q.Rear = -1; // phan tu cuoi o -1 (khong co phan tu trong Q)     Q.count = 0; //so phan tu bang 0 }

1.2 Kiểm tra Queue rỗng, đầy

Kiểm tra rỗng đầy chỉ cần kiểm tra count so với 0 và max

01 02 03 04 05 06 07 08 09 10 11 12 13

int Isempty (Queue Q) //kiem tra Queue rong {     if (Q.count == 0) //so phan tu = 0 => rong         return 1;     return 0; } int Isfull (Queue Q) //kiem tra Queue day {     if (Q.count == Max) //so phan tu = Max => day         return 1;     return 0; }

1.3 Thêm phần tử vào cuối Queue (Push)

Tăng vị trí của Rear lên 1 và đưa data vào vị trí đó

1 2 3 4 5 6 7 8 9

void Push(Queue Q, item x) //them phan tu vao cuoi Queue {     if (Isfull(Q)) printf("Hang doi day !");     else     {         Q.Data[++Q.Rear] = x; //tang Rear len va gan phan tu vao         Q.count++; //tang so phan tu len     } }

1.4 Xóa phần tử đầu Queue (Pop)

Trước tiên phải kiểm tra Queue rỗng không, nếu không rỗng ta thực hiện di chuyển các phần tử trong hàng về đầu hàng bằng vòng for (giống như xếp hàng khi mua hàng) sau đó giảm Rear và count xuống.

01 02 03 04 05 06 07 08 09 10 11 12 13

int Pop(Queue Q) //Loai bo phan tu khoi dau hang doi {     if (Isempty(Q)) printf("Hang doi rong !");     else     {         item x = Q.Data[Q.Front];         for (int i=Q.Front; i<Q.Rear; i++) //di chuyen cac phan tu ve dau hang             Q.Data[i] = Q.Data[i+1];         Q.Rear--; // giam vi tri phan tu cuoi xuong         Q.count--;//giam so phan tu xuong         return x; //tra ve phan tu lay ra     } }

1.5 Xem thông tin phần tử đầu Queue

1 2 3 4 5

item Qfront (Queue Q) //xem thong tin phan tu dau hang {     if (Isempty(Q)) printf("Hang doi rong !");     else return Q.Data[Q.Front]; }

1.6 hàng đợi vòng (Queue Circular)

Như trên chúng ta xây dựng Queue dựa vào mảng, và thấy 1 điểm bất lợi là khi xóa phần tử đầu Queue chúng ta cần di chuyển tất cả các phần tử phía sau về trước. Để khắc phục điều này chúng ta có thể coi mảng đó như 1 mảng với các phân tử được xếp vòng tròn.

Khi đó ta có thể thêm, xóa các phần tử đơn giản, tuy nhiên cần lưu ý khi thêm và xóa phần tử mà Rear và Front ở cuối mảng (Max-1). Để khắc phục ta chia Front và Rear lây dư cho Max. Vậy là Nếu Front và Rear ở Max thì sẽ trở về vị trí 0.

01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 17 18 19

void Push_Circular(Queue Q, item x) //them phan tu vao cuoi hang doi vong {     if (Isfull(Q)) printf("Hang doi day !");     else     {         Q.Data[(++Q.Rear) % Max] = x;         //tang Rear len va gan phan tu vao, Neu Rear dang o vi tri Max-1 thi tang ve vi tri 0         Q.count++; //tang so phan tu len     } } int Pop_Circular(Queue &Q) //Loai bo phan tu khoi dau hang doi vong {     if (Isempty(Q)) printf("Hang doi rong !");     item x = Q.Data[Q.Front];     Q.Front = (Q.Front++) % Max; // tang vi tri phan dau tien len, neu dang o Max-1 thi ve 0     Q.count--;//giam so phan tu xuong     return x; //tra ve phan tu lay ra }

2. Queue cài đặt bằng con trỏ

2.1 Xây dựng cấu trúc

01 02 03 04 05 06 07 08 09 10 11

typedef int item; //kieu du lieu class Node {     item Data;     Node Next; }; class Queue {     Node Front, Rear; //Node dau va Node cuoi     int count; //dem so phan tu };

2.2 Khởi tạo.

Khởi tạo Queue ta cho Front và Rear cùng trỏ về NULL, count =0.

1 2 3 4 5

void Init(Queue Q) {     Q.Front = Q.Rear = NULL;     Q.count = 0; }

2.3. Kiểm tra rỗng

1 2 3 4 5 6

int Isempty (Queue Q) //kiem tra Queue rong {     if (Q.count == 0) //so phan tu = 0 => rong         return 1;     return 0; }

2.4 Tạo 1 Node P

1 2 3 4 5 6 7

Node MakeNode(item x) //tao 1 Node {     Node P = (Node) malloc(sizeof(Node));     P.Next = NULL;     P.Data = x;     return P; }

2.5 Thêm phần tử vào cuối Queue

Để thêm phần tử, ta kiểm tra xem hàng có rỗng không, nếu hàng rỗng thì cho cả Front và Rear cùng trỏ về Node P mới tạo chứa phàn tử x cần thêm. Nếu không rỗng ta trỏ Rear->Next về P và Rear trỏ về P. Tăng count lên 1

01 02 03 04 05 06 07 08 09 10 11 12 13 14

void Push(Queue Q, item x) //them phan tu vao cuoi Queue {     Node P = MakeNode(x); //Neu Q rong     if (Isempty(Q))     {         Q.Front = Q.Rear = P; //dau va cuoi deu tro den P     }     else //Khong rong     {         Q.Rear.Next = P;         Q.Rear = P;     }     Q.count ++ ; //tang so phan tu len }

2.6 Xóa phần tử đầu Queue

Ta kiểm tra Queue có rỗng không, Nếu không rỗng kiểm tra xem có 1 hay nhiêu hơn 1 phần tử, nếu có 1 phần tử thì ta khởi tạo lại Queue, nếu có nhiều hơn ta cho Front trỏ đến tiếp theo. Giảm count xuống 1.

01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 17 18

int Pop(Queue Q) //Loai bo phan tu khoi dau hang doi {     if (Isempty(Q))     {         printf("Hang doi rong !");         return 0;     }     else     {         item x = Q.Front.Data;         if (Q.count == 1) //neu co 1 phan tu             Init(Q);         else             Q.Front = Q.Front.Next;         Q.count --;         return x; //tra ve phan tu lay ra     } }