Chương trình C++ triển khai hàng đợi (Queue) bằng danh sách liên kết

Hàng đợi (Queue) là cấu trúc dữ liệu trừu tượng tuân theo cơ chế FIFO (First In First Out) - phần tử vào trước được lấy ra trước.

Ví dụ

#include <iostream>
using namespace std;

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

struct node* front = NULL;
struct node* rear = NULL;
struct node* temp;

void Insert() {
    int val;
    cout << "Insert the element in queue: " << endl;
    cin >> val;
    if (rear == NULL) {
        rear = (struct node*)malloc(sizeof(struct node));
        rear->next = NULL;
        rear->data = val;
        front = rear;
    } else {
        temp = (struct node*)malloc(sizeof(struct node));
        rear->next = temp;
        temp->data = val;
        temp->next = NULL;
        rear = temp;
    }
}

void Delete() {
    temp = front;
    if (front == NULL) {
        cout << "Underflow" << endl;
        return;
    } else if (temp->next != NULL) {
        temp = temp->next;
        cout << "Element deleted from queue is: " << front->data << endl;
        free(front);
        front = temp;
    } else {
        cout << "Element deleted from queue is: " << front->data << endl;
        free(front);
        front = NULL;
        rear = NULL;
    }
}

void Display() {
    temp = front;
    if ((front == NULL) && (rear == NULL)) {
        cout << "Queue is empty" << endl;
        return;
    }
    cout << "Queue elements are: ";
    while (temp != NULL) {
        cout << temp->data << " ";
        temp = temp->next;
    }
    cout << endl;
}

int main() {
    int ch;
    cout << "1) Insert element to queue" << endl;
    cout << "2) Delete element from queue" << endl;
    cout << "3) Display all the elements of queue" << endl;
    cout << "4) Exit" << endl;
    do {
        cout << "Enter your choice: " << endl;
        cin >> ch;
        switch (ch) {
            case 1: Insert(); break;
            case 2: Delete(); break;
            case 3: Display(); break;
            case 4: cout << "Exit" << endl; break;
            default: cout << "Invalid choice" << endl;
        }
    } while(ch != 4);
    return 0;
}

Kết quả

1) Insert element to queue
2) Delete element from queue
3) Display all the elements of queue
4) Exit
Enter your choice: 1
Insert the element in queue: 4
Enter your choice: 1
Insert the element in queue: 3
Enter your choice: 1
Insert the element in queue: 5
Enter your choice: 2
Element deleted from queue is: 4
Enter your choice: 3
Queue elements are: 3 5
Enter your choice: 7
Invalid choice
Enter your choice: 4
Exit

Hàm Insert() - Thêm phần tử

Nếu rear là NULL → hàng đợi rỗng, tạo nút đầu tiên. Ngược lại, thêm nút mới sau rear và cập nhật rear.

void Insert() {
    int val;
    cout << "Insert the element in queue: " << endl;
    cin >> val;
    if (rear == NULL) {
        rear = (struct node*)malloc(sizeof(struct node));
        rear->next = NULL;
        rear->data = val;
        front = rear;
    } else {
        temp = (struct node*)malloc(sizeof(struct node));
        rear->next = temp;
        temp->data = val;
        temp->next = NULL;
        rear = temp;
    }
}

Hàm Delete() - Xóa phần tử

Nếu front là NULL → Underflow. Nếu chỉ có một phần tử → xóa và đặt front, rear = NULL. Ngược lại, xóa front và di chuyển front sang nút tiếp theo.

void Delete() {
    temp = front;
    if (front == NULL) {
        cout << "Underflow" << endl;
        return;
    } else if (temp->next != NULL) {
        temp = temp->next;
        cout << "Element deleted from queue is: " << front->data << endl;
        free(front);
        front = temp;
    } else {
        cout << "Element deleted from queue is: " << front->data << endl;
        free(front);
        front = NULL;
        rear = NULL;
    }
}

Hàm Display() - Hiển thị

Duyệt từ front đến cuối danh sách bằng con trỏ temp.

void Display() {
    temp = front;
    if ((front == NULL) && (rear == NULL)) {
        cout << "Queue is empty" << endl;
        return;
    }
    cout << "Queue elements are: ";
    while (temp != NULL) {
        cout << temp->data << " ";
        temp = temp->next;
    }
    cout << endl;
}

Hàm main() - Menu điều khiển

int main() {
    int ch;
    cout << "1) Insert element to queue" << endl;
    cout << "2) Delete element from queue" << endl;
    cout << "3) Display all the elements of queue" << endl;
    cout << "4) Exit" << endl;
    do {
        cout << "Enter your choice: " << endl;
        cin >> ch;
        switch (ch) {
            case 1: Insert(); break;
            case 2: Delete(); break;
            case 3: Display(); break;
            case 4: cout << "Exit" << endl; break;
            default: cout << "Invalid choice" << endl;
        }
    } while(ch != 4);
    return 0;
}