Deque の用途、メリット、デメリット

Deque (両端キュー) は、両端キューと同様の機能を提供する順次線形コレクション データ キューです。このデータ構造では、メソッドはデータ処理の先入れ先出し (FIFO) ルールに従いません。要素はキューの最後に挿入され、先頭から削除されるため、このデータ構造はデキューとも呼ばれます。 deque を使用すると、両端からのデータの追加と削除のみが可能になります。デキュー操作の時間計算量は O(1) です。デックには 2 つのタイプがあります -

• 入力制限あり

• シングルエンド入力制限。

• データを両端から削除できるようにします。

• 出力制限

• シングルエンド出力制限。

• # データを両端に挿入できるようにします。

次のコマンドは、コーダーが両端キューのデータセット プーリングを使用してさまざまな操作を実行するのに役立ちます -

• push_back() - 両端キューの後ろから要素を挿入します。

• push_front() - 両端キューの先頭から要素を挿入します。

• pop_back() - 両端キューの後ろから要素を削除します。

• pop_front() - 両端キューの先頭から要素を削除します。

• front() -両端キューの先頭要素を返します。

• back() -両端キューの後ろにある要素を返します。

• at() - 指定されたインデックスを設定/返します。

• size() - 要素の数を返します。

• empty() -両端キューが空の場合は true を返します。

円形配列では両端のキュー操作を使用できます。配列がいっぱいの場合は、プロセスを最初から開始できます。ただし、線形配列の場合、配列がいっぱいの場合、それ以上データを挿入できません。次に、「オーバーフローポップアップ」が表示されます。

両端キューの適用

Deque には、多数のリアルタイム アプリケーションが用意されています。

• はジョブ スケジューリング アプリケーションに使用されます。

• 時計回りと反時計回りの回転操作を O(1) 時間で実行できます。

• 両端キュー アルゴリズムは Web ブラウザの歴史にも存在します。

• ソート時の元に戻す操作に使用されます。

両端キューの利点

Deque には多くの利点があります。

• データを前後から追加・削除できます。

• サイズは動的です。

• Deque は、操作を実行するための効率的なタイミングを提供します。

• ここではLIFOスタックが使用されます。

• ここでは再割り当てできません。

• これは、適切な同期を備えたスレッドセーフなプロセスです。

• キャッシュに優しい。

両端キューの欠点

両端キューの欠点は次のとおりです。

• Deque プロセスのメモリ消費率は高くなります。

• マルチスレッド同期の問題があります。

• すべてのプラットフォームで利用できるわけではありません。

• 並べ替え操作の実装には適していません。

• Deque には機能が少ないです。

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

• ステップ 1 - サイズ n の両端キュー配列を考えます。

• ステップ 2 - 2 つのポインターを「front=-1」(フロントの場合) と「rear=0」(セットの場合) に設定します。

このプロセスには多くのサブ部分があります。両端キューで複数の操作を実行できます。ここではそれらをまとめます。

• deque の前からデータを挿入するためのアルゴリズム:-

• ステップ 1 - 前の位置を確認します。

• ステップ 2 - 「front
• ステップ 3 - それ以外の場合は、「front」を 1 減らす必要があります。

• ステップ 4 - 新しいキー要素を配列の先頭に追加します。

• deque の後にデータを挿入するためのアルゴリズム:-

• ステップ 1 - アレイがいっぱいかどうかを確認します。

• ステップ 2 - いっぱいの場合は、「rear=0」を適用します。

• ステップ 3 - それ以外の場合は、「rear」の値を 1 増やします。

• ステップ 4 - 新しいキーを「array[rear]」に再度追加します。

• 両端キューの前からデータを削除するためのアルゴリズム:-

• ステップ 1 -両端キューが空かどうかを確認します。

• ステップ 2 - リストが空 (「front=-1」) の場合、アンダーフロー状態であるため、削除は実行できません。

• ステップ 3 -両端キューに要素が 1 つしかない場合。すると「フロント＝リア＝－１」となります。

• ステップ 4 - それ以外の場合は、「front」が最後にあり、「front=0」に設定します。

• ステップ 5 - それ以外の場合、front=front 1。

• 両端キューの後ろからデータを削除するためのアルゴリズム:-

• ステップ 1 -両端キューが空かどうかを確認します。

• ステップ 2 - 空の場合 (「front=-1」)、削除は実行できません。これはアンダーフロー状態です。

• ステップ 3 - デキューにデータが 1 つしかない場合は、「front=rear=-1」になります。

• ステップ 4 - それ以外の場合は、以下の手順に従います。

• ステップ 5 - リアがフロントの場合は、「rear=0」です。前方「後方 = n-1」に進みます。

• ステップ 6 - それ以外の場合、rear=rear-1。

• 両端キューが空かどうかを確認するアルゴリズム:-

• ステップ 1 - フロント=-1 の場合、両端キューは空です。

• 両端キューがいっぱいかどうかを確認するアルゴリズム:-

• ステップ 1 - 前=0、後=n-1の場合

• ステップ 2 - または、フロント=リア 1

両端キューの構文

リーリー

データ構造では、両端キューはスタックとキューのいくつかのプロパティを継承します。 C では、デキューはベクトルのベクトルとして実装されます。

両端キューを使った各種メソッドの処理

• 方法 1 - 一般的な方法で両端キューを実装する

• 方法 2 - 要素を両端キューに挿入する

• 方法 3 - デキューから要素にアクセスする

• 方法 4 - デキューの要素を変更する

両端キューの一般的な実装

この C ビルド コードでは、一般的な方法で deque 操作を構成します。この例では、キューのバックエンドに要素を挿入します。これにより、システム全体がどのように実行されます。

例 1

リーリー ＃＃＃出力＃＃＃ リーリー

両端キューに要素を挿入

このコードでは、要素を両端キューに挿入する C コードを作成しようとしています。これを行うには 2 つの方法があります。

push_back() - 配列の最後に要素を挿入します。
push_front() - 配列の先頭に要素を挿入します。
例 2

リーリー ＃＃＃出力＃＃＃ リーリー

両端キューからの要素へのアクセス

2 つの方法を使用して両端キュー内の要素にアクセスできます。

front() - フロントで戻り値を取得できます。

• back() - 次のデータを返します。

• at() - 指定されたインデックスから戻ります。

• リーリー ＃＃＃出力＃＃＃ リーリー

  両端キューの要素の変更

このコードでは、at() メソッドを使用して、特定の両端キューの要素を置換または変更できます。

例 4

リーリー ＃＃＃出力＃＃＃ リーリー ＃＃＃結論は＃＃＃

この記事を通じて、両端キュー、その操作方法、用途、メリットとデメリット、アルゴリズムと C を使用した可能なコードについて学びました。

以上がDeque の用途、メリット、デメリットの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。