コンピューター サイエンスにおけるキューは、コンポーネントが「先入れ先出し」(FIFO) の原則に従って一方の端に入れられ、もう一方の端から取り出される線形データ構造です。このデータ構造は、アクションシーケンスの制御やデータの保存に利用できます。 C は、配列またはリンク リストの形式で組み込まれたキュー機能を備えたコンピューター言語です。
特徴:
- キューは、配列またはリンク リストを使用して構築できる線形データ構造の一種です。
- 要素はキューの先頭から削除されながら、キューの最後尾に再配置されます。
- エンキュー (要素を後ろに追加する) とデキュー (要素を前から削除する) は 2 つのキュー操作です。
- 要素の追加と削除が頻繁に行われる場合、メモリの無駄を防ぐためにキューが循環キューとして構築されることがあります。
配列の使用:
配列を使用して C でキューを実装するには、まずキューの最大サイズを定義し、そのサイズの配列を宣言します。前部と後部の整数はそれぞれ 1 に設定されました。前部の変数はキューの前部の要素を表し、後部の変数は後部の要素を表します。
新しい要素をキューの最終位置にプッシュする前に、back 変数を 1 増やす必要があります。キューは現在いっぱいで、back 位置がキューの最大容量に達すると、他の要素を追加できません。キューの先頭に要素を追加し、キューから要素を削除する場合のみ、先頭の変数を 1 つ増やします。前方と後方の位置が等しく、これ以上コンポーネントを削除できない場合、キューは空であると言えます。
以下は、配列を使用する C で書かれたキューのインスタンスです。
C プログラミング言語:
#define MAX_SIZE 100 int queue[MAX_SIZE]; int front = -1; int rear = -1; void enqueue(int element) { if (rear == MAX_SIZE - 1) { printf('Queue is full'); return; } if (front == -1) { front = 0; } rear++; queue[rear] = element; } int dequeue() { if (front == -1 || front > rear) { printf('Queue is empty'); return -1; } int element = queue[front]; front++; return element; } int main() { enqueue(10); enqueue(20); enqueue(30); printf('%d ', dequeue()); printf('%d ', dequeue()); printf('%d ', dequeue()); printf('%d ', dequeue()); return 0; } コードの出力は次のようになります。
出力：
10 20 30 Queue is empty-1
説明：
- まず、3 つの要素 10、20、および 30 をキューにエンキューします。
- 次に、キューの先頭の要素 (10) をデキューして出力します。
- 次に、キューの先頭要素 (20) を再度デキューして出力します。
- 次に、キューをデキューして、キューの先頭の要素 (30) を再度出力します。
- 最後に、空のキューからデキューを行い、「キューは空です」を出力し、-1 を返します。
リンクリストの使用:
プログラミング言語 C でキューを構築するもう 1 つの代替アプローチは、リンク リストを使用することです。このメソッドを使用すると、キュー内の各ノードは、要素値を含むノードと、キュー内の次のノードへのポインタによって表現されます。キュー内の最初と最後のノードをそれぞれ追跡するために、フロント ポインターとリア ポインターが使用されます。
要素値を使用して新しいノードを確立し、その次のポインタを NULL に設定して要素をキューに追加します。キューが空の場合、新しいノードにフロント ポインタとリア ポインタを設定します。そうでない場合は、後部ポインタを更新し、古い後部ノードの次のポインタが新しいノードを指すように設定します。
キューからノードを削除する場合、まず前のノードが削除され、次にフロント ポインタがキュー内の後続のノードに更新され、最後に削除されたノードが占有していたメモリが解放されます。削除後にフロント ポインタが NULL の場合、キューは空です。
ダイアナ・メアリー・ブラッカー
以下は、リンク リストを使用して C で実装されたキューの例です。
C プログラミング言語:
#include #include struct Node { int data; struct Node* next; }; struct Node* front = NULL; struct Node* rear = NULL; void enqueue(int element) { struct Node* new_node = (struct Node*)malloc(sizeof(struct Node)); new_node->data = element; new_node->next = NULL; if (front == NULL && rear == NULL) { front = rear = new_node; return; } rear->next = new_node; rear = new_node; } int dequeue() { if (front == NULL) { printf('Queue is empty'); return -1; } struct Node* temp = front; int element = temp->data; if (front == rear) { front = rear = NULL; } else { front = front->next; } free(temp); return element; } int main() { enqueue(10); enqueue(20); enqueue(30); printf('%d ', dequeue()); printf('%d ', dequeue()); printf('%d ', dequeue()); printf('%d ', dequeue()); return 0; } コードの出力は次のようになります。
出力：
10 20 30 Queue is empty-1
説明：
- まず、3 つの要素 10、20、および 30 をキューにエンキューします。
- 次に、キューの先頭の要素 (10) をデキューして出力します。
- 次に、キューの先頭要素 (20) を再度デキューして出力します。
- 次に、キューをデキューして、キューの先頭の要素 (30) を再度出力します。
- 最後に、空のキューからデキューしようとします。これにより、「キューが空です」というメッセージが出力され、-1 が返されます。
利点:
- キューは、幅優先検索やタスク スケジューリングなど、要素を正確な順序で処理する必要があるアルゴリズムを実装する場合に特に役立ちます。
- キュー操作の時間計算量は O(1) であるため、巨大なキューでも高速に実行できます。
- キューは、配列またはリンク リストを使用して簡単に実装できるため、特に柔軟です。
短所:
- スタックとは異なり、キューは単一のポインターで構築できないため、キューの実装は少し複雑になります。
- キューが配列として構築されている場合、追加される要素が多すぎるとすぐにいっぱいになる可能性があり、その結果、パフォーマンスの問題が発生したり、クラッシュが発生したりする可能性があります。
- リンクされたリストを使用してキューを実装する場合、特に小さな要素の場合、各ノードのメモリ オーバーヘッドが大きくなる可能性があります。
結論：
重要なデータ構造であるキューを使用するアプリケーションには、ほんの数例を挙げると、オペレーティング システム、ネットワーク、ゲームなどがあります。これらは配列またはリンク リストを使用して簡単に作成できるため、要素を特定の順序で処理する必要があるアルゴリズムに最適です。ただし、キューには、メモリ消費量や実装の複雑さなど、特定のアプリケーションのデータ構造を選択するときに考慮する必要がある欠点があります。