Header Ads

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í đó
push
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.
pop
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.
Circular
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ỏ

queue pointer

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
push
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.
pop
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
    }
}

Không có nhận xét nào

Được tạo bởi Blogger.