C言語を使用して配列ベースのキューを実装する方法

プログラミングでは、キューは一般的に使用されるデータ構造であり、Java の Queue や Python の deque など、多くのプログラミング言語には独自のキュー実装があります。ただし、C 言語には既製のキュー実装がありません。したがって、C 言語では、配列を定義し、ポインタやその他のトリックを使用してキューを実装する必要があります。

この記事では、C言語を使用して配列ベースのキューを実装する方法を紹介します。

1. キュー構造の定義

キュー構造を定義することで、キュー操作を実装できます。このキュー構造には、キューのサイズ、先頭ポインタと末尾ポインタ、要素データなどの情報が含まれます。

#define MAX_SIZE 100

typedef struct queue {
    int size;
    int front;
    int rear;
    int data[MAX_SIZE];
} Queue;

上記のコードでは、キューの最大サイズを表す MAX_SIZE 定数を定義し、構造体を定義して Queue という名前のキューを宣言します。

このうち、sizeはキューのサイズ、frontはキュー先頭ポインタ、rearはキュー末尾ポインタ、dataは要素を格納する配列です。

2. キュー初期化操作

キューの実装では、キューを正しく使用できるようにするために、最初にキュー初期化操作を実行する必要があります。

void init(Queue *q) {
    q->size = 0;
    q->front = 0;
    q->rear = -1;
}

上記のコードでは、初期化関数 init を定義します。この関数は、キュー構造を指すポインタ q をパラメータとして受け取り、キューのサイズを 0、ヘッド ポインタを 0、およびポインタは -1 に設定され、キューが空であることを示します。

3. 要素のキューイング操作

キューのエンキュー操作は、要素をキューの最後に配置することです。ここでの実装は、要素を最後に追加することです。配列 data の位置を更新し、後方ポインタの位置を更新します。

int enqueue(Queue *q, int value) {
    if(q->size == MAX_SIZE) {
        return 0;
    }
    q->rear++;
    q->data[q->rear] = value;
    q->size++;
    return 1;
}

上記のコードでは、最初にキューがいっぱいかどうかを判断します。いっぱいの場合は、挿入が失敗したことを示す 0 を返します。それ以外の場合は、後方ポインタが 1 位置および要素値だけ後方に移動されます。がデータ配列末尾に割り当てられ、キュー サイズに 1 が加算され、最後に挿入が成功したことを示す 1 が返されます。

4. 要素のデキュー操作

キューのデキュー操作は、キューの先頭の要素を取り出し、先頭ポインターの位置を更新することです。ここで実装されているアイデアは、データの先頭位置にある要素の値を返し、先頭ポインターを 1 ビット後方に移動し、同時にキューのサイズを更新することです。

int dequeue(Queue *q) {
    if(q->size == 0) {
        return -1;
    }
    int value = q->data[q->front];
    q->front++;
    q->size--;
    return value;
}

上記のコードでは、まずキューが空かどうかを判定します。空の場合は、キューが空であることを示す -1 を返します。それ以外の場合は、データの先頭の要素の値を返し、フロントポインタを後方に移動します。1 ビット、キューサイズを 1 減分し、要素の値を返します。

5. テスト キューの実装

キューのさまざまな操作を実装したので、テストしてみましょう:

#include <stdio.h>

int main() {
    Queue myQueue;
    init(&myQueue);
    enqueue(&myQueue, 1);
    enqueue(&myQueue, 2);
    enqueue(&myQueue, 3);
    printf("%d\n", dequeue(&myQueue));
    printf("%d\n", dequeue(&myQueue));
    printf("%d\n", dequeue(&myQueue));
    return 0;
}

コード内の上記のテストでは、まず myQueue という名前のキューを定義し、init 関数を使用して初期化します。次に、エンキュー関数を使用して数字 1、2、および 3 をキューに挿入し、デキュー関数を使用してキューから要素を削除して画面に出力します。

ここでの出力は次のようになります:

1
2
3

6. 要約

この記事では、C 言語を使用して配列ベースのキューを実装する方法を学習しました。 。キュー構造と関連する操作関数を定義することで、キュー内の要素の追加、削除、アクセスが簡単に行えます。ポインタを使用してキューを実装するのは面倒ですが、この方法はキューの原理をより深く理解するのに役立ち、データ構造とアルゴリズムを学習するのに非常に役立ちます。

以上がC言語を使用して配列ベースのキューを実装する方法の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。