double ended queue c with examples
C ++のDequeまたは両端キューに関する詳細なチュートリアル。チュートリアルでは、Deque、基本操作、C ++およびJavaの実装とアプリケーションとは何かについて説明しています。
両端キューまたは単に「Deque」と呼ばれるものは、Queueの一般化されたバージョンです。
QueueとDequeの違いは、FIFO（First In、First Out）アプローチに従わないことです。 Dequeの2番目の機能は、フロントエンドまたはリアエンドのいずれかから要素を挿入および削除できることです。
学習内容：
両端キューの分類
Dequeは次のように分類できます。
制限付きタッチ入力。 入力制限では、削除は両端から実行できますが、挿入はキューの後端でのみ実行できます。
出力制限された両端キュー： 出力制限キューでは、挿入は両端から実行できますが、削除は一方の端、つまりキューのフロントエンドでのみ実行されます。
dequeを使用してスタックとキューを実装することもできます。
基本的なタッチ操作
以下は、dequeで実行できる基本的な操作です。
- フロントを挿入： dequeの前にアイテムを挿入または追加します。
- insertLast： dequeの後ろにアイテムを挿入または追加します。
- deleteFront： キューの先頭からアイテムを削除または削除します。
- 最後に削除： キューの後ろからアイテムを削除または削除します。
- getFront： dequeのフロントアイテムを取得します。
- getLast： キューの最後のアイテムを取得します。
- isEmpty： dequeが空かどうかを確認します。
- 一杯： dequeがいっぱいかどうかを確認します。
とイラスト
空の両端キューは次のように表されます。
次の操作のうち、ポインタに適用できなかったものはどれですか
次に、要素1を前面に挿入します。
ここで、要素3を背面に挿入します。
次に、要素5を前面に追加し、前面をインクリメントすると4になります。
次に、要素7を後部に挿入し、要素9を前部に挿入します。 dequeは次のようになります。
次に、正面から要素を削除しましょう。
したがって、要素が前面に挿入されると前面の位置が減少し、要素が削除されると前面の位置が増加することがわかります。後端の場合、位置は挿入のためにインクリメントされ、削除のためにデクリメントされます 。
および実装
100 ++タッチの実装
配列とリンクリストを使用して、C ++で両端キューを実装できます。これとは別に、標準テンプレートライブラリ（STL）には、このデータ構造のすべての関数を実装するクラス「deque」があります。
dequeの配列実装を以下に示します。両端キューであるため、実装には循環配列を使用しました。
#include using namespace std; #define MAX_size 10 // Maximum size of array or Dequeue // Deque class class Deque { int array(MAX_size); int front; int rear; int size; public : Deque(int size) { front = -1; rear = 0; this->size = size; } // Operations on Deque: void insertfront(int key); void insertrear(int key); void deletefront(); void deleterear(); int getFront(); int getRear(); // Check if Deque is full bool isFull()front == rear+1); // Check if Deque is empty bool isEmpty(){ return (front == -1); } }; // Insert an element at front of the deque void Deque::insertfront(int key) { if (isFull()) { cout << 'Overflow!!
' << endl; return; } // If queue is initially empty,set front=rear=0; start of deque if (front == -1) { front = 0; rear = 0; } else if (front == 0) // front is first position of queue front = size - 1 ; else // decrement front 1 position front = front-1; array(front) = key ; // insert current element into Deque } // insert element at the rear end of deque void Deque ::insertrear(int key) { if (isFull()) { cout << ' Overflow!!
' << endl; return; } // If queue is initially empty,set front=rear=0; start of deque if (front == -1) { front = 0; rear = 0; } else if (rear == size-1) // rear is at last position of queue rear = 0; else // increment rear by 1 position rear = rear+1; array(rear) = key ; // insert current element into Deque } // Delete element at front of Deque void Deque ::deletefront() { if (isEmpty()) { cout << 'Queue Underflow!!
' << endl; return ; } // Deque has only one element if (front == rear) { front = -1; rear = -1; } else // back to initial position if (front == size -1) front = 0; else // remove current front value from Deque;increment front by 1 front = front+1; } // Delete element at rear end of Deque void Deque::deleterear() { if (isEmpty()) { cout << ' Underflow!!
' << endl ; return ; } // Deque has only one element if (front == rear) { front = -1; rear = -1; } else if (rear == 0) rear = size-1; else rear = rear-1; } // retrieve front element of Deque int Deque::getFront() { if (isEmpty()) { cout << ' Underflow!!
' << endl; return -1 ; } return array(front); } // retrieve rear element of Deque int Deque::getRear() { if(isEmpty() || rear < 0) { cout << ' Underflow!!
' << endl; return -1 ; } return array(rear); } //main program int main() { Deque dq(5); cout << 'Insert element 1 at rear end
'; dq.insertrear(1); cout << 'insert element 3 at rear end
'; dq.insertrear(3); cout << 'rear element of deque ' << ' ' << dq.getRear() << endl; dq.deleterear(); cout << 'After deleterear, rear = ' << dq.getRear() << endl; cout << 'inserting element 5 at front end
'; dq.insertfront(5); cout << 'front element of deque ' << ' ' << dq.getFront() << endl; dq.deletefront(); cout << 'After deletefront, front = ' << dq.getFront() << endl; return 0; } 出力：
エレメント1を後端に挿入します
後端にエレメント3を挿入します
deque3のリアエレメント
deleterearの後、rear = 1
フロントエンドにエレメント5を挿入
deque5のフロント要素
deletefrontの後、front = 1
注目すべきモノのインターネット企業
Java実装の再集計
Javaのdequeインターフェース「java.util.Deque」は「java.util.Queue」インターフェースから派生しています。 Dequeは、キュー（先入れ先出し）またはスタック（後入れ先出し）として使用できます。これらの実装は、リンクリストよりも高速に動作します。
以下に示すのは、JavaのDequeインターフェースの階層です。
JavaのDequeインターフェースに関するいくつかのポイントを覚えておく必要があります。
- 外部同期がないため、実装はスレッドセーフではありません。
- Dequeは、複数のスレッドによる同時実行をサポートしていません。
- 配列を使用して実装されたDequeは、NULL要素の使用を許可しません。
- アレイは要件に応じて拡張でき、制限のない容量とサイズ変更可能なアレイのサポートが2つの最も重要な機能です。
以下は、Dequeインターフェースでサポートされているさまざまなメソッドです。
Javaインタビューコーディングの質問と回答
| 番号。 | 方法 | 説明 |
|---|---|---|
| 7 | iterator（） | dequeのイテレータを返します。 |
| 1 | add（element） | 尾に要素を追加します。 |
| 二 | addFirst（element） | 頭/正面に要素を追加します。 |
| 3 | addLast（element） | テール/リアに要素を追加します。 |
| 4 | オファー（要素） | 尾に要素を追加します。挿入が成功したかどうかを示すブール値を返します。 |
| 5 | オファーファースト（要素） | 頭に要素を追加します。挿入が成功したかどうかを示すブール値を返します。 |
| 6 | オファーラスト（要素） | 尾に要素を追加します。挿入が成功したかどうかを示すブール値を返します。 |
| 8 | 降順Iterator（） | この両端キューの順序が逆のイテレータを返します。 |
| 9 | push（element） | dequeの先頭に要素を追加します。 |
| 10 | pop（要素） | dequeのヘッドから要素を削除し、それを返します。 |
| 十一 | removeFirst（） | dequeの先頭にある要素を削除します。 |
| 12 | removeLast（） | dequeの末尾にある要素を削除します。 |
| 13 | poll（） | dequeの最初の要素（dequeのヘッドで表される）を取得して削除します。 dequeが空の場合、NULLを返します。 |
| 14 | pollFirst（） | この両端キューの最初の要素を取得して削除します。この両端キューが空の場合はnullを返します。 |
| 15 | pollLast（） | この両端キューの最後の要素を取得して削除します。この両端キューが空の場合はnullを返します。 |
| 16 | ピーク（） | この両端キューで表されるキューの先頭（両端キューの最初の要素）を取得します。この両端キューが空の場合はnullを返します。 注：この操作では、要素は削除されません。 |
| 17 | peekFirst（） | この両端キューの最初の要素を取得します。この両端キューが空の場合はnullを返します。 注：この操作では、要素は削除されません。 |
| 18 | peekLast（） | この両端キューの最後の要素を取得するか、この両端キューが空の場合はnullを返します。 注：この操作では、要素は削除されません。 |
次のJava実装は、上記のさまざまな操作を示しています。
import java.util.*; class Main { public static void main(String() args) { Deque deque = new LinkedList (); // We can add elements to the queue in various ways deque.add(1); // add to tail deque.addFirst(3); deque.addLast(5); deque.push(7); //add to head deque.offer(9); deque.offerFirst(11); deque.offerLast(13); System.out.println('The deque : ' + deque + '
'); // Iterate through the queue elements. System.out.println('Standard Iterator'); Iterator iterator = deque.iterator(); while (iterator.hasNext()) System.out.print(' ' + iterator.next()); // Reverse order iterator Iterator reverse = deque.descendingIterator(); System.out.println('
Reverse Iterator'); while (reverse.hasNext()) System.out.print(' ' + reverse.next()); // Peek returns the head, without deleting // it from the deque System.out.println('
Peek ' + deque.peek()); System.out.println('After peek: ' + deque); // Pop returns the head, and removes it from // the deque System.out.println('
Pop ' + deque.pop()); System.out.println('After pop: ' + deque); // We can check if a specific element exists // in the deque System.out.println('
Contains element 3?: ' + deque.contains(3)); // We can remove the first / last element. deque.removeFirst(); deque.removeLast(); System.out.println('Deque after removing ' + 'first and last elements: ' + deque); } } 出力：
そして(11、7、3、1、5、9、13)
標準イテレータ
11 7 3 1 5 9 13
リバースイテレータ
13 9 5 1 3 7 11
ピーク11
ピーク後：(11、7、3、1、5、9、13)
ポップ11
ポップ後：(7、3、1、5、9、13)
要素3が含まれていますか？：true
最初と最後の要素を削除した後の両端キュー：(3、1、5、9)
上記のプログラムでは、JavaのDequeインターフェースを使用し、整数要素のdequeを定義しました。次に、この両端キューに対してさまざまな操作を実行し、これらの操作の結果を出力して表示します。
アプリケーション
Dequeは、次のアプリケーションの一部で使用できます。
＃1）スケジューリングアルゴリズム： スケジューリングアルゴリズム「A-stealスケジューリングアルゴリズム」は、マルチプロセッサシステムのさまざまなプロセッサのタスクスケジューリングを実装します。この実装はdequeを使用し、プロセッサはdequeから最初の要素を取得して実行します。
＃2）アクティビティのリストを元に戻す： ソフトウェアアプリケーションでは、多くのアクションがあります。 1つは「元に戻す」です。元に戻すアクションを何度も実行すると、これらのアクションはすべてリストに保存されます。このリストは両端キューとして保持されるため、どの端からでもエントリを簡単に追加/削除できます。
＃3） しばらくしてからエントリを削除します。 アプリは、在庫エントリを一覧表示するアプリなど、リスト内のエントリを更新します。これらのアプリは、しばらくするとエントリを削除し、新しいエントリを挿入します。これは、両端キューを使用して行われます。
結論
Dequeは両端キューであり、キューの両端、つまり前面と背面から要素を追加/削除できます。 Dequeは、配列またはリンクリストを使用して実装できます。ただし、Dequeのさまざまな操作を実装するStandard Template Library（STL）クラスもあります。
Javaには、Dequeを実装するためにキューインターフェイスから継承されるDequeインターフェイスがあります。 Dequeの基本的な標準操作とは別に、このインターフェイスはDequeで実行できる他のさまざまな操作をサポートします。
Dequeは通常、両端から要素を追加/削除する必要があるアプリケーションに使用されます。また、主にマルチプロセッサシステムのプロセッサのスケジューリングにも使用されます。