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

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

キューの実際の例としては、車両が最初に進入し、最初に退出する単一車線の一方通行道路があります。より現実的な例は、切符売り場やバス停の列として見ることができます。

キュー表現

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

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

基本操作

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

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

上記のキュー操作を効率化するために必要な関数はこれ以上ありません。これらは-

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

キューでは、常にデータをデキュー（またはアクセス）します。 front ポインタとキュー内のデータをクエリ（または保存）している間、私たちは助けを借ります rear ポインター。

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

ピーク（）

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

Algorithm

begin procedure peek
   return queue[front]
end procedure

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

Example

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

一杯（）

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

Algorithm

begin procedure isfull

   if rear equals to MAXSIZE
      return true
   else
      return false
   endif
   
end procedure

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

Example

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

isempty（）

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

Algorithm

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プログラミングコードです-

Example

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

エンキュー操作

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

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

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

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

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

procedure enqueue(data)      
   
   if queue is full
      return overflow
   endif
   
   rear ← rear + 1
   queue[rear] ← data
   return true
   
end procedure

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

Example

int enqueue(int data)      
   if(isfull())
      return 0;
   
   rear = rear + 1;
   queue[rear] = data;
   
   return 1;
end procedure

デキュー操作

キューからのデータへのアクセスは、2つのタスクのプロセスです。 frontアクセス後にデータをポイントして削除します。実行するには、次の手順を実行しますdequeue 操作-

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

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

procedure dequeue
   
   if queue is empty
      return underflow
   end if

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

end procedure

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

Example

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

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

   return data;
}

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