データ構造とアルゴリズム-キュー

キューは抽象的なデータ構造で、Stacksに多少似ています。スタックとは異なり、キューは両端で開いています。一方の端は常にデータの挿入（エンキュー）に使用され、もう一方の端はデータの削除（デキュー）に使用されます。キューは先入れ先出し法に従います。つまり、最初に保存されたデータ項目が最初にアクセスされます。

キューの例

キューの実際の例は、車線が最初に出て最初に出る単一車線の片道です。より現実的な例は、チケットの窓口やバス停の待ち行列として見ることができます。

キュー表現

現在、キューでそれを理解しているので、さまざまな理由で両端にアクセスします。以下に示す次の図は、キュー構造をデータ構造として説明しようとしています-

キューの例

スタックと同様に、キューは配列、リンクリスト、ポインター、および構造体を使用して実装することもできます。簡単にするために、1次元配列を使用してキューを実装します。

基本操作

キュー操作には、キューの初期化または定義、キューの使用、メモリからの完全消去が含まれます。ここでは、キューに関連付けられている基本的な操作を理解しようとします-

* enqueue（）*-アイテムをキューに追加（保存）します。
* dequeue（）*-キューからアイテムを削除（アクセス）します。

上記のキュー操作を効率的にするには、さらに多くの機能が必要です。これらは-

* peek（）*-キューの先頭にある要素を削除せずに取得します。
* isfull（）*-キューがいっぱいかどうかを確認します。
* isempty（）*-キューが空かどうかを確認します。

キューでは、常に front ポインターが指すデータをデキュー（またはアクセス）し、キューにデータをキュー（または格納）する際に rear ポインターを使用します。

最初にキューのサポート機能について学びましょう-

ピーク（）

この関数は、キューの*先頭*にあるデータを確認するのに役立ちます。 peek（）関数のアルゴリズムは次のとおりです-

アルゴリズム

begin procedure peek
   return queue[front]
end procedure

Cプログラミング言語でのpeek（）関数の実装-

例

int peek() {
   return queue[front];
}

一杯（）

1次元配列を使用してキューを実装しているため、後方のポインターがMAXSIZEに到達するようにチェックして、キューがいっぱいであることを判断します。循環リンクリストでキューを維持する場合、アルゴリズムは異なります。 isfull（）関数のアルゴリズム-

アルゴリズム

begin procedure isfull

   if rear equals to MAXSIZE
      return true
   else
      return false
   endif

end procedure

Cプログラミング言語でのisfull（）関数の実装-

例

bool isfull() {
   if(rear == MAXSIZE - 1)
      return true;
   else
      return false;
}

isempty（）

isempty（）関数のアルゴリズム-

アルゴリズム

begin procedure isempty

   if front is less than MIN  OR front is greater than rear
      return true
   else
      return false
   endif

end procedure

*front* の値がMINまたは0より小さい場合、キューはまだ初期化されていないため、空であることを示します。

ここにCプログラミングコードがあります-

例

bool isempty() {
   if(front < 0 || front > rear)
      return true;
   else
      return false;
}

エンキュー操作

キューは、 front と rear の2つのデータポインターを保持します。したがって、その操作は、スタックの操作よりも実装が比較的困難です。

キューにデータをエンキュー（挿入）するには、次の手順を実行する必要があります-

*ステップ1 *-キューがいっぱいかどうかを確認します。
*ステップ2 *-キューがいっぱいの場合、オーバーフローエラーを生成して終了します。
ステップ3 *-キューがいっぱいでない場合は、 *rear ポインターをインクリメントして、次の空のスペースを指します。
*ステップ4 *-後方が指しているキューの場所にデータ要素を追加します。
*ステップ5 *-成功を返します。

挿入操作

予期しない状況を処理するために、キューが初期化されているかどうかを確認することもあります。

エンキュー操作のアルゴリズム

procedure enqueue(data)

   if queue is full
      return overflow
   endif

   rear ← rear + 1
   queue[rear] ← data
   return true

end procedure

Cプログラミング言語でのenqueue（）の実装-

例

int enqueue(int data)
   if(isfull())
      return 0;

   rear = rear &plus; 1;
   queue[rear] = data;

   return 1;
end procedure

デキュー操作

キューからのデータへのアクセスは、2つのタスクのプロセスです- front が指しているデータにアクセスし、アクセス後にデータを削除します。 *デキュー*操作を実行するには、次の手順が取られます-

*ステップ1 *-キューが空かどうかを確認します。
*ステップ2 *-キューが空の場合、アンダーフローエラーを生成して終了します。
ステップ3 *-キューが空でない場合、 *front が指しているデータにアクセスします。
ステップ4 *-次の利用可能なデータ要素を指すように *front ポインタをインクリメントします。
*ステップ5 *-成功を返します。

操作の削除

デキュー操作のアルゴリズム

procedure dequeue

   if queue is empty
      return underflow
   end if

   data = queue[front]
   front ← front + 1
   return true

end procedure

Cプログラミング言語でのdequeue（）の実装-

例

int dequeue() {
   if(isempty())
      return 0;

   int data = queue[front];
   front = front + 1;

   return data;
}

Cプログラミング言語の完全なキュープログラムについては、リンクしてください：/data_structures_algorithms/queue_program_in_c [ここをクリック]。

Data-structures-algorithms-dsa-queue

目次

データ構造とアルゴリズム-キュー

キュー表現

基本操作

ピーク（）

一杯（）

isempty（）

エンキュー操作

エンキュー操作のアルゴリズム

デキュー操作

デキュー操作のアルゴリズム