定義
デック(Deque、Double-Ended Queue)は両端から挿入と削除が可能なデータ構造です。スタックとキューの特性を兼ね備え、柔軟に使用できます。
主な特性
- ✓両端でO(1)時間で挿入/削除可能
- ✓スタックとして使用可能（片端のみ使用）
- ✓キューとして使用可能（両端で異なる操作）
- ✓スライディングウィンドウアルゴリズムでよく使用
活用事例
こんな場面で使われます:
🪟
スライディングウィンドウ最大/最小
ウィンドウ内の最大/最小値をO(n)で求める際にデックを活用します。両端から削除が可能だからです。
🔄
回文チェック
両端から文字を取り出して比較し、回文かどうかを効率的にチェックできます。
📋
タスクスケジューリング
優先度の高いタスクを前に、低いタスクを後ろに追加して柔軟に管理します。
🌐
ブラウザ履歴
訪問履歴を両端で管理し、進む/戻る機能を実装します。
主な操作
主な操作:
pushFront
O(1)デックの先頭に要素を挿入します。
pushBack
O(1)デックの末尾に要素を挿入します。
popFront
O(1)先頭の要素を削除して返します。
popBack
O(1)末尾の要素を削除して返します。
peekFront / peekBack
O(1)先頭/末尾の要素を削除せずに確認します。
計算量
時間計算量
最良
O(1)
平均
O(1)
最悪
O(1)
空間計算量
O(n)
可視化でより深く理解する
ステップごとのアニメーションとコード実行を通じて、アルゴリズムの動作を直接確認してください。
可視化を開始