Ngoài cách cài đặt queue bằng mảng, ta cũng có thể cài đặt queue bằng danh sách lên kết. Ta hoàn toàn có thể tạo một hàng đợi sử dụng một DSLK đơn. Trong đó phần tử đầu danh sách liên kết (pHead) chính là phần tử đầu của queue và phần tử cuối danh sách liên kết (pTail) chính là phần tử cuối của queue. Dưới đây là các thao tác cơ bản trên Queue khi cài đặt bằng danh sách liên kết:

• Khởi tạo queue: Init (q)
• Kiểm tra queue rỗng: IsEmpty (q)
• Tạo mới một nút chứa dữ liệu x: CreateNode(x)
• Thêm phần tử vào queue: Add(q, x)
• Lấy phần tử ra khỏi queue: Remove (q)

1.Khai báo các node và cấu trúc queue với danh sách liên kết

Các phần tử của queue khi được cài đặt bằng danh sách liên kết sẽ được coi là một node. Vì vậy ta cần khai báo một node có 2 thành phần đó là: thành phần data và thành phần liên kết (con trỏ Next). Ở đoạn code dưới đây tôi khai báo node lưu trữ cho kiểu int data,các bạn hoàn toàn có thể thay đổi kiểu dữ liệu sao cho phù hợp với bài toán của mình. Ví dụ: float data, char data, double data, SinhVien data…

struct node{
    int data;
    node *next;
};
typedef struct node NODE;

Tiếp theo ta sẽ khai báo một hàng đợi queue ban đầu gồm hai Node đó là NODE *front; và NODE *rear; (hai node này giống NODE *pHead và NODE *pTail trong danh sách liên kết đơn)

struct queue{
    NODE *front;
    NODE *rear;
};
typedef struct queue QUEUE;

2.Hàm khởi tạo và kiểm tra queue bằng danh sách liên kết

2.1 Hàm khởi tạo queue

Khi cài đặt queue bằng danh sách liên kết, ta có thể khởi tạo queue đó bằng cách gán trực tiếp NODE *front và NODE *rear bằng giá trị NULL.

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 front và rear bằng NULL.

void Init(QUEUE &q){
    //gan front va rear ve NULL
    q.front = NULL;
    q.rear = NULL;
}

2.2 Hàm tạo một node trong queue

Như đã đề cập ở trên, một node gồm 2 thành phần là: thành phần data và thành phần liên kết vì thế mà ta cần phải tạo một node để chứa được 2 thành phần này.

Node này sau khi được khởi tạo sẽ được đưa vào hàng đợi và coi chúng như một phần tử của hàng đợi.

Hàm NODE* CreateNode(int x) dưới đây nhận int x là dữ liệu cần thêm vào Node khi được khởi tạo.

NODE* CreateNode (int x) {
    NODE *p;
    p = new NODE;
    //neu p = NULL thi ko du bo nho cap phat
    if (p==NULL) {
        printf ("KHONG DU BO NHO!");
        return NULL;
    }
    //gan data bang X
    p->data=x;
    //gan con tro next bang NULL
    p->next=NULL;
    //tra ve node p
    return p;
}

2.3 Hàm kiểm tra rỗng trong queue

Hàm kiểm tra rỗng có chức năng kiểm tra queue có đang là rỗng hay không? Việc kiểm tra này là cần thiết và thường được thực hiện trước khi sử dụng thao tác lấy phần tử ở queue. Để kiểm tra queue có rỗng hay không ta chỉ cần kiểm tra NODE *front của queue đó có bằng NULL hay không? Nếu front bằng NULL thì queue đó đang rỗng và ngược lại thì queue đó không rỗng!

int IsEmpty(QUEUE q){
    //neu front bang NULL thi queue rong
    if (q.front == NULL){
        return 1;
    }
    //nguoc lai tra ve 0
    return 0;
}

3.Thao tác add và remove với queue bằng danh sách liên kết

3.1 Thao tác add trong queue

Thao tác add là việc thêm một phần tử (hay một Node) vào trong hàng đợi. Node khi được thêm vào hàng đợi luôn luôn được đặt vào cuối hàng đợi đó.

Hàm void Add(QUEUE &q, NODE *NewNode) dưới đây nhận QUEUE &q là hàng đợi cần thêm phần tử và NODE *NewNode là phần tử (hay node) sẽ được thêm vào cuối hàng đợi.

void Add (QUEUE &q, NODE *NewNode){
    //neu hang doi rong thi them node moi vao ca dau va cuoi hang doi
    if(q.front == NULL){
        q.front = NewNode;
        q.rear = NewNode;
    }
    else{//nguoc lai them cuoi hang doi
        //dat con tro next cua phan tu cuoi ve NewNode
        q.rear->next = NewNode;
        //gan lai phan tu cuoi cua danh sach
        q.rear = NewNode;
    }
}

3.2 Thao tác remove trong queue

Thao tác remove trong queue sẽ thực hiện lấy phần tử (hay node) ở đầu hàng đợi đó ra và đồng thời thực hiện xóa đi phần tử đó.

Hàm int Remove(QUEUE &q) dưới đây nhận QUEUE &q là hàng đợi cần lấy ra phần tử đầu và đồng thời xoá đi phần tử đó. Hàm này sẽ trả về giá trị int bởi vì ta đang cài đặt queue lưu trữ các giá trị là số nguyên int.

int Remove(QUEUE &q){
    int x;
    NODE *p = NULL;
    //neu queue khong rong thuc hien lay phan tu dau queue
    if (!IsEmpty(q)){
        //gan node p bang phan tu dau tien cua queue
        p = q.front;
        //gan du lieu cua node p vao x
        x = p->data;
        //xoa di node dau tien cua queue
        q.front = q.front->next;
        delete p;
        //neu front bang NULL thi gan luon rear bang NULL
        if (q.front==NULL){
            q.rear = NULL;
        }
    }
    //tra ve du lieu x vua lay ra
    return x;
}

4.Nhập xuất node vào trong queue

Ta có thể xây dựng các hàm nhập xuất các node vào trong queue thông qua hàm void Add() và hàm void Remove() ở trên. Việc nhập sẽ là hành động nhập N phần tử (hay Node) vào trong queue.

Hàm nhập N node vào trong queue như sau:

void Input(QUEUE &q, int n){
    //duyet N lan
    for(int i = 0; i< n; i++){
        //nhap phan tu vao bien x
        int x;
        printf("Nhap phan tu thu %d: ",i);
        scanf("%d", &x);
        printf("\n");
        //tao node p co du lieu la x
        NODE *p;
        p = CreateNode(x);
        //them node p vao queue
        Add(q,p);
    }
}

Hàm xuất các node trong queue ra màn hình (nhưng không xóa) sẽ được viết như sau:

void Output(QUEUE q){
    //duyet tu dau den cuoi hang doi
    for(NODE *p = q.front; p!= NULL; p=p->next){
        //hien thi data cua cac node
        printf("%d\n",p->data);
    }
}

5.Chương trình cài đặt hàng đợi queue bằng danh sách liên kết

Ta cần một số thư viện nhất định dưới đây để cài đặt được queue bằng danh sách liên kết:

#include<stdio.h>
#include<stdlib.h>

Nếu bạn đã học quá kỹ về cấu trúc danh sách liên kết đơn thì các hàm trên có vẻ rất quen thuộc. Khi cài đặt hàng đợi bằng danh sách liên kết việc ta thêm phần tử giống như thêm vào cuối trong danh sách liên kết đơn và việc lấy ra phần tử tương tự như việc xóa đầu trong danh sách liên kết đơn.

#include <stdio.h>
#include <stdlib.h>
struct node{
    int data;
    node *next;
};
typedef struct node NODE;

struct queue{
    NODE *front;
    NODE *rear;
};
typedef struct queue QUEUE;

void Init(QUEUE &q){
    //gan front va rear ve NULL
    q.front = NULL;
    q.rear = NULL;
}

NODE* CreateNode (int x) {
    NODE *p;
    p = new NODE;
    //neu p = NULL thi ko du bo nho cap phat
    if (p==NULL) {
        printf ("KHONG DU BO NHO!");
        return NULL;
    }
    //gan data bang X
    p->data=x;
    //gan con tro next bang NULL
    p->next=NULL;
    //tra ve node p
    return p;
}

int IsEmpty(QUEUE q){
    //neu front bang NULL thi queue rong
    if (q.front == NULL){
        return 1;
    }
    //nguoc lai tra ve 0
    return 0;
}

void Add (QUEUE &q, NODE *NewNode){
    //neu hang doi rong thi them node moi vao ca dau va cuoi hang doi
    if(q.front == NULL){
        q.front = NewNode;
        q.rear = NewNode;
    }
    else{//nguoc lai them cuoi hang doi
        //dat con tro next cua phan tu cuoi ve NewNode
        q.rear->next = NewNode;
        //gan lai phan tu cuoi cua danh sach
        q.rear = NewNode;
    }
}

int Remove(QUEUE &q){
    int x;
    NODE *p = NULL;
    //neu queue khong rong thuc hien lay phan tu dau queue
    if (!IsEmpty(q)){
        //gan node p bang phan tu dau tien cua queue
        p = q.front;
        //gan du lieu cua node p vao x
        x = p->data;
        //xoa di node dau tien cua queue
        q.front = q.front->next;
        delete p;
        //neu front bang NULL thi gan luon rear bang NULL
        if (q.front==NULL){
            q.rear = NULL;
        }
    }
    //tra ve du lieu x vua lay ra
    return x;
}

void Input(QUEUE &q, int n){
    //duyet N lan
    for(int i = 0; i< n; i++){
        //nhap phan tu vao bien x
        int x;
        printf("Nhap phan tu thu %d: ",i);
        scanf("%d", &x);
        //tao node p co du lieu la x
        NODE *p;
        p = CreateNode(x);
        //them node p vao queue
        Add(q,p);
    }
}

void Output(QUEUE q){
    //duyet tu dau den cuoi hang doi
    for(NODE *p = q.front; p!= NULL; p=p->next){
        //hien thi data cua cac node
        printf("%d \t",p->data);
    }
}

int main(){
    //tao moi queue
    QUEUE q;
    //khoi tao queue
    Init(q);
    //nhap n phan tu vao queue
    int n;
    printf("NHAP N: ");
    scanf("%d", &n);
    Input(q,n);
    //hien thi phan tu trong queue
    printf("CAC PHAN TU TRONG HANG DOI LA\n");
    Output(q);
    //them mot node co du lieu bang 66 vao hang doi
    int x = 66;
    NODE *p = CreateNode(x);
    Add(q,p);
    printf("\nHANG DOI SAU KHI THEM NODE %d \n",x);
    Output(q);
    //thuc hien lay phan tu trong hang doi ra
    int k = Remove(q);
    printf("\nHANG DOI SAU KHI REMOVE %d \n",k);
    Output(q);
}