Deque（双方向キュー）：両端からの挿入と削除
先頭と後方の両方でO(1)での挿入と削除をサポートするdequeについて学びます。実装、スライディングウィンドウ問題、スタックやキューとの比較を理解します。
Queue
詳細な説明
Deque（双方向キュー）
deque（「デック」と発音）はスタックとキューの両方の一般化です。先頭と後方の両方での挿入と削除を許可します。
操作
| 操作 | 説明 | 計算量 |
|---|---|---|
pushFront(x) |
先頭に挿入 | O(1) |
pushBack(x) |
後方に挿入 | O(1) |
popFront() |
先頭から削除 | O(1) |
popBack() |
後方から削除 | O(1) |
Dequeによるスタックとキューのシミュレーション
dequeは両方をシミュレートできます：
- スタック：
pushBackとpopBackを使用。 - キュー：
pushBackとpopFrontを使用。
スライディングウィンドウ最大値（クラシック問題）
最も有名なdequeアルゴリズムは「サイズkの各ウィンドウの最大値」をO(n)で解きます。dequeは減少順に要素を維持します。新しい要素より小さい要素は後方からpopされ、ウィンドウ外の要素は先頭からpopされます。
言語実装
| 言語 | 実装 |
|---|---|
| Python | collections.deque |
| Java | ArrayDeque, LinkedList |
| C++ | std::deque |
| JavaScript | 組み込みなし（配列またはカスタム） |
| Go | 組み込みなし（container/listまたはカスタム） |
ユースケース
Dequeはコーディング面接や実世界のストリーム処理で頻繁に登場するスライディングウィンドウ問題に不可欠です。ワークスティーリングスレッドスケジューラはdequeを使用します。最大履歴サイズ付きのブラウザの元に戻す/やり直しは、制限に達したときに最も古いエントリをエビクトするためにdequeを使用します。