logo

TechCodeview

Deque (または両端キュー)

この記事では、両端キューまたは両端キューについて説明します。まずキューについて簡単に説明します。

キューとは何ですか?

キューは、最初に来たものが最初に出力されるデータ構造であり、FIFO (先入れ先出し) ポリシーに従います。キューへの挿入は、として知られる一方の端から行われます。 後部 または しっぽ、 一方、削除は、として知られる別の端から行われます。 フロントエンド または 頭 キューの。

Javaと比較してください

実際の行列の例は、映画館のホールの外にあるチケットの列です。この場合、列の最初に入場した人が最初にチケットを受け取り、列の最後に入場した人が最後にチケットを受け取ります。

Deque (または両端キュー) とは何ですか

deque は Double Ended Queue の略です。 Deque は、挿入および削除操作が両端から実行される線形データ構造です。 deque はキューの一般化されたバージョンであると言えます。

デキュー内の挿入と削除は両端で実行できますが、FIFO ルールに従いません。両端キューの表現は次のように与えられます。

Deque (または両端キュー)

デックの種類

デックには 2 つのタイプがあります -

  • 入力制限キュー
  • 出力制限付きキュー

入力制限付きキュー

入力制限キューでは、挿入操作は片端からのみ行えますが、削除は両端から行うことができます。

Deque (または両端キュー)

出力制限付きキュー

出力制限キューでは、削除は片端のみで、挿入は両端から行うことができます。

Deque (または両端キュー)

デキューに対して実行される操作

デキューに適用できる次の操作があります。

  • 前から挿入
  • 後部挿入
  • 先頭の削除
  • 後ろの削除

上記の操作に加えて、両端キューでピーク操作を実行することもできます。ピーク操作を通じて、両端子クエリの前後の要素を取得できます。したがって、上記の操作に加えて、次の操作も deque でサポートされています。

AWSSNS
  • 両端キューから先頭の項目を取得します
  • 両端キューから後ろの項目を取得します
  • 両端キューがいっぱいかどうかを確認する
  • 両端キューが空かどうかを確認します

ここで、例を使用して deque に対して実行される操作を理解しましょう。

フロントエンドでの挿入

この操作では、要素はキューのフロントエンドから挿入されます。操作を実装する前に、まずキューがいっぱいかどうかを確認する必要があります。キューがいっぱいでない場合は、以下の条件を使用してフロントエンドから要素を挿入できます。

  • キューが空の場合、後部と前部の両方が 0 で初期化されます。これで、両方とも最初の要素を指すようになります。
  • それ以外の場合は、フロントが 1 未満である場合はフロントの位置を確認します (フロント<1), then reinitialize it by front = n - 1、つまり配列の最後のインデックス。
Deque (または両端キュー)

後端に挿入

この操作では、キューの後端から要素が挿入されます。操作を実装する前に、まずキューがいっぱいかどうかを再度確認する必要があります。キューがいっぱいでない場合は、以下の条件を使用して要素を後端から挿入できます。

スプリングブーツ
  • キューが空の場合、後部と前部の両方が 0 で初期化されます。これで、両方とも最初の要素を指すようになります。
  • それ以外の場合は、後部を 1 だけインクリメントします。後部が最後のインデックス (またはサイズ - 1) である場合、それを 1 増やす代わりに、0 に等しくする必要があります。
Deque (または両端キュー)

フロントエンドでの削除

この操作では、要素がキューのフロントエンドから削除されます。操作を実装する前に、まずキューが空かどうかを確認する必要があります。

キューが空の場合、つまりフロント = -1 の場合、アンダーフロー状態となり、削除を実行できません。キューがいっぱいでない場合は、以下の条件を使用してフロントエンドから要素を挿入できます。

両端キューに要素が 1 つしかない場合は、rear = -1 およびfront = -1 を設定します。

それ以外の場合、フロントが末尾にある場合 (フロント = サイズ - 1 を意味します)、フロント = 0 を設定します。

それ以外の場合は、フロントを 1 つ増やします (つまり、フロント = フロント + 1)。

Javaの部分文字列メソッド
Deque (または両端キュー)

後端の削除

この操作では、キューの後端から要素が削除されます。操作を実装する前に、まずキューが空かどうかを確認する必要があります。

キューが空の場合、つまりフロント = -1 の場合、アンダーフロー状態となり、削除を実行できません。

両端キューに要素が 1 つしかない場合は、rear = -1 およびfront = -1 を設定します。

リア = 0 (リアがフロント) の場合、リア = n - 1 を設定します。

それ以外の場合は、後部を 1 減分します (または、後部 = 後部 -1)。

Deque (または両端キュー)

空のチェックを入れる

この操作は、両端キューが空かどうかを確認するために実行されます。フロント = -1 の場合、両端キューが空であることを意味します。

フルチェック

この操作は、両端キューがいっぱいかどうかを確認するために実行されます。フロント = リア + 1、またはフロント = 0 およびリア = n - 1 の場合、両端キューがいっぱいであることを意味します。

デキューの上記のすべての操作の時間計算量は O(1)、つまり一定です。

デックの応用

  • Deque はスタックとキューの両方の操作をサポートしているため、スタックとキューの両方として使用できます。
  • Deque は回文チェッカーとして使用できます。これは、文字列を両端から読み取ると、文字列が同じになることを意味します。

デックの実装

ここで、C プログラミング言語での deque の実装を見てみましょう。

int を文字列 Java にキャストします 
 #include #define size 5 int deque[size]; int f = -1, r = -1; // insert_front function will insert the value from the front void insert_front(int x) { if((f==0 &amp;&amp; r==size-1) || (f==r+1)) { printf(&apos;Overflow&apos;); } else if((f==-1) &amp;&amp; (r==-1)) { f=r=0; deque[f]=x; } else if(f==0) { f=size-1; deque[f]=x; } else { f=f-1; deque[f]=x; } } // insert_rear function will insert the value from the rear void insert_rear(int x) { if((f==0 &amp;&amp; r==size-1) || (f==r+1)) { printf(&apos;Overflow&apos;); } else if((f==-1) &amp;&amp; (r==-1)) { r=0; deque[r]=x; } else if(r==size-1) { r=0; deque[r]=x; } else { r++; deque[r]=x; } } // display function prints all the value of deque. void display() { int i=f; printf(&apos;
Elements in a deque are: &apos;); while(i!=r) { printf(&apos;%d &apos;,deque[i]); i=(i+1)%size; } printf(&apos;%d&apos;,deque[r]); } // getfront function retrieves the first value of the deque. void getfront() { if((f==-1) &amp;&amp; (r==-1)) { printf(&apos;Deque is empty&apos;); } else { printf(&apos;
The value of the element at front is: %d&apos;, deque[f]); } } // getrear function retrieves the last value of the deque. void getrear() { if((f==-1) &amp;&amp; (r==-1)) { printf(&apos;Deque is empty&apos;); } else { printf(&apos;
The value of the element at rear is %d&apos;, deque[r]); } } // delete_front() function deletes the element from the front void delete_front() { if((f==-1) &amp;&amp; (r==-1)) { printf(&apos;Deque is empty&apos;); } else if(f==r) { printf(&apos;
The deleted element is %d&apos;, deque[f]); f=-1; r=-1; } else if(f==(size-1)) { printf(&apos;
The deleted element is %d&apos;, deque[f]); f=0; } else { printf(&apos;
The deleted element is %d&apos;, deque[f]); f=f+1; } } // delete_rear() function deletes the element from the rear void delete_rear() { if((f==-1) &amp;&amp; (r==-1)) { printf(&apos;Deque is empty&apos;); } else if(f==r) { printf(&apos;
The deleted element is %d&apos;, deque[r]); f=-1; r=-1; } else if(r==0) { printf(&apos;
The deleted element is %d&apos;, deque[r]); r=size-1; } else { printf(&apos;
The deleted element is %d&apos;, deque[r]); r=r-1; } } int main() { insert_front(20); insert_front(10); insert_rear(30); insert_rear(50); insert_rear(80); display(); // Calling the display function to retrieve the values of deque getfront(); // Retrieve the value at front-end getrear(); // Retrieve the value at rear-end delete_front(); delete_rear(); display(); // calling display function to retrieve values after deletion return 0; }

出力：

Deque (または両端キュー)

それでは、この記事については以上です。この記事があなたにとって有益で有益であることを願っています。