Bài trước, tôi đã giới thiệu qua về việc cài đặt hàng đợi queue bằng mảng. Trong bài này chúng ta sẽ cùng đi chi tiết hơn về việc cài đặt hàng đợi queue bằng mảng trong ngôn ngữ C/C++. Các thao tác cần có khi cài đặt hàng đợi queue bằng mảng đó là:

• Khởi tạo Queue: Init (q)
• Kiểm tra Queue rỗng: IsEmpty (q)
• Kiểm tra Queue đầy: IsFull (q)
• Thêm phần tử vào Queue: Add(q, x)
• Lấy phần tử ra khỏi Queue: Remove (q)

Trước khi đi vào chi tiết các thao tác trên ta có hàng đợi khi cài đặt bằng mảng sẽ được khai báo như sau:

#define MAX 100
typedef struct queue
{
    int A[MAX];
    int front, rear;
};
typedef struct queue QUEUE;

1.Hàm khởi tạo và kiểm tra hàng đợi queue bằng mảng

1.1 Hàm khởi tạo queue

Để khởi tạo hàng đợi ta cần có lệnh khởi tạo front = 0 và rear = -1 sẽ tạo ra một queue rỗng, sau khi thực hiện khởi tạo thành công ta sẽ đảm bảo các thao tác trên queue được thực hiện đúng đắn.

Hàm void Init(QUEUE &q) dưới đây nhận QUEUE &q là hàng đợi cần khởi tạo và thực hiện gán int front = 0; và int rear = -1;

void Init(QUEUE &q){
    //gan front bang 0
    q.front = 0;
    //gan rear bang -1
    q.rear = -1;
}

1.2 Hàm kiểm tra queue rỗng

Trước khi thực hiện việc lấy phần tử trong hàng đợi ra, ta cần phải đảm bảo việc kiểm tra queue đó là không rỗng. Nếu queue là rỗng thì không được phép lấy phần tử. Ở phần khởi tạo hàng đợi ta đã gán int front = 0; và int rear = -1; (nghĩa là front > rear ), vì vậy để kiểm tra rằng hàng đợi có là rỗng hay không ta chỉ cần thực hiện kiểm tra nếu front > rear thì hàng đợi đó đang rỗng, ngược lại thì không rỗng!

int IsEmpty(QUEUE q){
    //neu front > rear thi hang doi rong va tra ve 1
    if (q.front > q.rear){
        return 1;
    }
    //nguoc lai khong rong thi tra ve 0
    return 0;
}

1.3 Kiểm tra queue đầy

Việc kiểm tra queue đã đầy hay chưa được gọi đến trước khi thực hiện thao tác đưa một phần tử vào queue. Nếu queue đó đầy thì phần tử cuối cùng của queue đó bằng MAX – 1 (trong đó MAX là số lượng phần tử mà ban đầu ta đã định nghĩa). Việc đó tương đương với việc so sánh int rear có bằng MAX – 1 hay không?

int IsFull (QUEUE q){
    //neu rear == MAX - 1 thi hang doi day va tra ve 1
    if (q.rear==MAX-1){
        return 1;
    }
    //nguoc lai hang doi chua day
    return 0;
}

2.Hàm add và hàm remove với queue bằng mảng

2.1 Hàm add trong queue

Add chính là thao tác thêm phần tử mới vào trong hàng đợi. Việc thêm phần tử mới vào hàng đợi queue luôn luôn đặt phần tử được thêm vào cuối hàng đợi.

Trước khi thêm vào hàng đợi ta sẽ kiểm tra xem hàng đợi đó đã đầy hay chưa, nếu chưa đầy thì thực hiện việc thêm phần tử vào cuối hàng đợi.

Hàm void Add(QUEUE &q, int x) nhận QUEUE &q là hàng đợi cần thêm phần tử và int x là giá trị phần từ cần thêm vào cuối hàng đợi.

void Add (QUEUE &q, int x){
    //Queue chưa đầy
    if (IsFull(q)==0) {
        //tang chi so rear len 1 don vi
        q.rear++;
        //them phan tu x vao cuoi hang doi
        q.A[q.rear] = x;
    }
}

2.2 Hàm remove trong queue

Thao tác remove chính là thao tác lấy phần tử trong hàng đợi ra và đồng thời xóa đi phần tử đó. Việc lấy phần tử của hàng đợi luôn được thực hiện bằng cách lấy phần tử ở đầu hàng đợi đó ra.

Hàm int Remove(QUEUE &q) nhận QUEUE &q là hàng đợi cần thực hiện lấy ra phần tử đầu, hàm này thực hiện trả về phần tử đầu tiên của hàng đợi và đồng thời xóa đi phần tử vừa được lấy ra.

int Remove(QUEUE &q){
    int x;
    //neu hang doi khong rong
    if (!IsEmpty(q)) {
        //gan x bang phan tu dau tien cua hang doi
        x = q.A[q.front];
        //tang bien front len 1 don vi
        q.front++;
        //tra ve phan tu lay duoc
        return x;
    }
    else{//nguoc lai hang doi rong
        front = 0; rear = -1;
    }
}

3.Nhập xuất phần tử trong mảng hàng đợi queue

Để nhập được N phần tử vào trong hàng đợi ta cần sử dụng lại hàm void Add() ở trên và kết hợp với vòng lặp for. Để thực hiện lấy ra tất cả phần tử cũng tương tự như vậy.

Hàm nhập N phần tử vào trong hàng đợi cài đặt bằng mảng như sau:

void Input(QUEUE &q, int n){
    //duyet tu 0 den n
    for(int i = 0; i< n; i++){
        //thuc hien nhap gia tri vao bien x
        int x;
        printf("Nhap gia tri phan tu thu %d: ",i);
        scanf("%d",&x);
        //thuc hien add phan tu x vao queue
        Add(q,x);
    }
}

Hàm xuất ra những phần tử có trong hàng đợi nhưng không xóa đi chúng được biểu diễn như sau:

void Output(QUEUE q){
    //duyet tu phan tu dau ve phan tu cuoi queue
    for(int i = q.front; i <= q.rear; i++){
        //hien thi ra ket qua
        printf("%d \t",q.A[i]);
    }
}

4.Chương trình cài đặt queue bằng mảng hoàn chỉnh

Chương trình hoàn chỉnh dưới đây được lắp ghép lại từ các hàm ở trên, vì vậy bạn nên đọc kỹ các phần ở trên trước khi đến chương trình hoàn chỉnh này!

#include <stdio.h>
#define MAX 100
typedef struct queue
{
    int A[MAX];
    int front, rear;
};
typedef struct queue QUEUE;

void Init(QUEUE &q){
    //gan front bang 0
    q.front = 0;
    //gan rear bang -1
    q.rear = -1;
}

int IsEmpty(QUEUE q){
    //neu front > rear thi hang doi rong va tra ve 1
    if (q.front > q.rear){
        return 1;
    }
    //nguoc lai khong rong thi tra ve 0
    return 0;
}

int IsFull (QUEUE q){
    //neu rear == MAX - 1 thi hang doi day va tra ve 1
    if (q.rear==MAX-1){
        return 1;
    }
    //nguoc lai hang doi chua day
    return 0;
}

void Add (QUEUE &q, int x){
    //Neu queue chua day
    if (IsFull(q)==0) {
        //tang chi so rear len 1 don vi
        q.rear++;
        //them phan tu x vao cuoi hang doi
        q.A[q.rear] = x;
    }
}

int Remove(QUEUE &q){
    int x;
    //neu hang doi khong rong
    if (!IsEmpty(q)) {
        //gan x bang phan tu dau tien cua hang doi
        x = q.A[q.front];
        //tang bien front len 1 don vi 
        q.front++;
        //tra ve phan tu lay duoc
        return x;
    }
    else{//nguoc lai hang doi rong

        q.front = 0; q.rear = -1;
    }
}

void Input(QUEUE &q, int n){
    //duyet tu 0 den n
    for(int i = 0; i< n; i++){
        //thuc hien nhap gia tri vao bien x
        int x;
        printf("Nhap gia tri phan tu thu %d: ",i);
        scanf("%d",&x);
        //thuc hien add phan tu x vao queue
        Add(q,x);
    }
}

void Output(QUEUE q){
    //duyet tu phan tu dau ve phan tu cuoi queue
    for(int i = q.front; i <= q.rear; i++){
        //hien thi ra ket qua
        printf("%d \t",q.A[i]);
    }
}

int main(){
    //khai bao hang doi
    QUEUE q;
    //khoi tao hang doi
    Init(q);
    //nhap N 
    int n;
    printf("NHAP N: ");
    scanf("%d",&n);
    //nhap N phan tu vao hang doi
    Input(q,n);
    //hien thi phan tu
    printf("Cac phan tu vua nhap vao queue la: \n");
    Output(q);
    //thao tac add
    int x = 66;
    Add(q,x);
    printf("\nHang doi sau khi add %d la: \n",x);
    Output(q);
    //thao tac lay ra phan tu hang doi
    int front = Remove(q);
    printf("\nHang doi sau khi remove phan tu %d la: \n",front);
    Output(q);
}