C++で連結リスト（リンクリスト）を使ってキューを実装する方法

キュー（queue）とは、複数の要素を格納するための抽象データ構造のひとつです。キューは「FIFO（First In First Out：先入れ先出し）」と呼ばれる仕組みに基づいて動作し、最初に挿入された要素が最初に削除されます。言い換えれば、キューの中では最も早く追加された要素から順に取り除かれることになります。

ここでは、連結リスト（リンクリスト）を用いてキューを実装するC++プログラムを紹介します。

サンプルプログラム

#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;
}

実行結果

上記プログラムの実行結果は次のようになります。

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

実行例では、まず4、3、5の順に要素を挿入し、その後に削除を行っています。FIFOの性質により、最初に挿入した「4」が最初に取り出されている点に注目してください。

プログラムの解説

Insert()関数：要素の挿入

上記プログラムでは、Insert()関数がキューへ要素を挿入します。rearがNULLの場合はキューが空であることを意味するため、新しいノードを1つ作成してそこに要素を格納し、frontとrearの両方がそのノードを指すようにします。キューに要素が既に存在する場合は、rearの後ろに新しいノードを連結し、そのノードを新しい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;
    }
}

Delete()関数：要素の削除

Delete()関数では、キューに要素がひとつも存在しない場合は「アンダーフロー（Underflow）」状態となります。キューに要素が1つしかない場合はその要素を削除し、frontとrearをNULLに戻します。要素が複数ある場合は、frontが指す先頭の要素を削除し、frontを次の要素へと移動させます。該当するコードは以下の通りです。

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;
    }
}

Display()関数：要素の表示

Display()関数では、frontとrearがどちらもNULLであればキューは空であると判断し、その旨を表示します。空でない場合は、一時変数tempを利用したwhileループによって、キュー内のすべての要素を先頭から順番に出力します。該当するコードは以下の通りです。

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;
}

main()関数：メニュー処理

main()関数は、ユーザーに対して「挿入」「削除」「表示」「終了」のいずれかの操作を選択させるメニューを提供します。ユーザーの入力に応じてswitch文で適切な関数を呼び出し、範囲外の値が入力された場合には「Invalid choice（無効な選択）」と出力します。do-whileループにより、ユーザーが「4（Exit）」を選択するまで処理が繰り返されます。該当するコードは以下の通りです。

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;
}

まとめ

連結リストを利用すれば、配列のような固定サイズの制約を受けずに、要素数が柔軟に変化するキューを実装できます。挿入はrear（末尾）側、削除はfront（先頭）側で行う構造にすることで、どちらの操作もO(1)の計算量で高速に処理できる点が大きなメリットです。データ構造の基本的な考え方を理解するうえでも、ぜひ実際にコードを動かして挙動を確認してみてください。