C言語で連結リストを使ったキューの実装方法【挿入・削除・表示を解説】

連結リスト（リンクリスト）を使ってキューを実装すれば、配列ベースの実装で問題になりやすい「キューのオーバーフロー（あふれ）」や「キューのアンダーフロー（枯渇）」を効果的に回避できます。

キューはFIFO（First In First Out：先入れ先出し）方式のデータ構造です。C言語では、連結リストを利用することでメモリを動的に確保しながら柔軟なキューを実装できます。連結リストによるキューに対する主な操作は次の2つです。

• 挿入（Insert / Enqueue）
• 削除（Delete / Dequeue）

挿入（Enqueue）

挿入は、キューの末尾（rear側）に新しい要素を追加する操作です。新しいノード用にメモリを確保し、キューが空かどうかで処理を分けます。構文は以下の通りです。

構文

&item :
Newnode = (node*) malloc(sizeof(node));
newnode->data = item;
newnode->link = NULL;
if ((front == NULL) || (rear == NULL)){
    front = newnode;
    rear = newnode;
}else{
    rear->link = newnode;
    rear = newnode;
}

削除（Dequeue）

削除は、キューの先頭（front側）から要素を取り出す操作です。キューが空の場合は削除できないため、その判定を行ってから不要になったノードを解放します。構文は以下の通りです。

構文

if ((front == NULL))
    printf("Deletion is not possible, Queue is empty");
else{
    temp = front;
    front = front->link;
    free(temp);
}

表示（Display）

表示は、先頭ノードから順に格納されているデータを出力していく操作です。構文は以下の通りです。

構文

while (front != NULL){
    printf("%d", front->data);
    front = front->link;
}

サンプルプログラム

以下は、連結リストを用いてキューを実装したC言語のプログラムです。メニュー形式で、エンキュー（挿入）・デキュー（削除）・表示・先頭要素の確認が行えます。

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

struct node {
    int info;
    struct node *ptr;
} *front, *rear, *temp, *front1;

int frontelement();
void enq(int data);
void deq();
void display();
void create();

int count = 0;

void main() {
    int no, ch, e;
    printf("\n 1 - Enqueue");
    printf("\n 2 - Dequeue");
    printf("\n 3 - Display");
    printf("\n 4 - Exit");
    printf("\n 5 - Front");
    create();
    while (1) {
        printf("\n Enter choice : ");
        scanf("%d", &ch);
        switch (ch) {
        case 1:
            printf("Enter data : ");
            scanf("%d", &no);
            enq(no);
            break;
        case 2:
            deq();
            break;
        case 3:
            display();
            break;
        case 4:
            exit(0);
            break;
        case 5:
            e = frontelement();
            if (e != 0)
                printf("Front element : %d", e);
            else
                printf("\n No front element in Queue");
            break;
        default:
            printf("Wrong choice, Try again ");
            break;
        }
    }
}

/* 挿入：キューの末尾に要素を追加 */
void enq(int data) {
    if (rear == NULL) {
        rear = (struct node *)malloc(1 * sizeof(struct node));
        rear->ptr = NULL;
        rear->info = data;
        front = rear;
    } else {
        temp = (struct node *)malloc(1 * sizeof(struct node));
        rear->ptr = temp;
        temp->info = data;
        temp->ptr = NULL;
        rear = temp;
    }
    count++;
}

/* 表示：先頭から順に出力 */
void display() {
    front1 = front;
    if ((front1 == NULL) && (rear == NULL)) {
        printf("Queue is empty");
        return;
    }
    while (front1 != rear) {
        printf("%d ", front1->info);
        front1 = front1->ptr;
    }
    if (front1 == rear)
        printf("%d", front1->info);
}

/* 削除：キューの先頭から要素を取り出す */
void deq() {
    front1 = front;
    if (front1 == NULL) {
        printf("\n Error");
        return;
    } else if (front1->ptr != NULL) {
        front1 = front1->ptr;
        printf("\n Dequeued value : %d", front->info);
        free(front);
        front = front1;
    } else {
        printf("\n Dequeued value : %d", front->info);
        free(front);
        front = NULL;
        rear = NULL;
    }
    count--;
}

/* 先頭要素の参照 */
int frontelement() {
    if ((front != NULL) && (rear != NULL))
        return (front->info);
    else
        return 0;
}

実行結果

上記のプログラムを実行すると、次のような結果が出力されます。

1 - Enque
2 - Deque
3 - Display
4 - Exit
5 - Front element
Enter choice: 1
Enter data: 14
Enter choice: 1
Enter data: 85
Enter choice: 1
Enter data: 38
Enter choice: 5
Front element: 14
Enter choice: 3
14 85 38
Enter choice: 2
Dequed value: 14
Enter choice: 3
Enter choice: 4

このように、連結リストを使ったキューは動的なメモリ確保によって要素数の制約を受けず、データ量に応じて柔軟に運用できるのが大きな利点です。なお、実際の開発では main 関数は int main(void) と宣言し、malloc の戻り値チェックや未定義の create() 関数の補完なども併せて行うことが推奨されます。