"Deque" (データ構造)

"Deque"

先端と末尾の両方で追加と削除が行える式のキューを表す．

詳細

  • デックは，先入れ先出しと後入れ先出しの挿入および削除の両方をサポートする要素の集合である：
  • CreateDataStructure["Deque"]新しい空の"Deque"を作成する
    CreateDataStructure["Deque",elems]elems を含む新しい"Deque"を作成する
    Typed[x,"Deque"]x に"Deque"型を与える
  • "Deque"型のデータ構造には，以下の演算が使える．
  • ds["Copy"]ds のコピーを返すtime: O(n)
    ds["DropAll"]ds からすべての要素を省くtime: O(n)
    ds["Elements"]ds の要素のリストを返すtime: O(n)
    ds["EmptyQ"]ds が空の場合にTrueを返すtime: O(1)
    ds["Fold",fun,init]fun を ds の要素に適用する．init で始めて，結果を累積するtime: O(n)
    ds["Length"]ds に含まれる要素の数time: O(1)
    ds["PeekBack"]ds の最後の要素time: O(1)
    ds["PeekFront"]ds の最初の要素 time: O(1)
    ds["PopBack"]ds の最後の要素を削除し，それを返すtime: O(1)
    ds["PopFront"]ds の最初の要素を削除し，それを返すtime: O(1)
    ds["PushBack",x]x を ds の末尾に加えるtime: O(1)
    ds["PushBackList",elems]elems を ds の末尾に加えるtime: O(nelems)
    ds["PushFront",x]x を ds の最初に加えるtime: O(1)
    ds["PushFrontList",elems]elems を ds の最初に加えるtime: O(nelems)
    ds["Visualization"]ds の可視化を返すtime: O(n)
  • 以下の関数もサポートする．
  • dsi===dsjdsi が dsj に等しい場合はTrue
    FullForm[ds]ds の完全形
    Information[ds]ds についての情報
    InputForm[ds]ds の入力形
    Normal[ds]ds を通常の式に変換する

例題

すべて開くすべて閉じる

例  (2)

新しい"Deque"は，CreateDataStructureを使って作成できる：

ds は最初は空である：

ds に要素を加える：

ds はもはや空ではない：

要素を1個含む：

別の要素を加えてからピークする．最初の要素が表示される：

最後の要素を削除し，それを返す：

式バージョンの ds を返す：

要素はキューに素早く加えることができる：

データ構造の可視化を生成することができる：

全要素を合計する：

スコープ  (1)

情報  (1)

新しい"Deque"は，CreateDataStructureを使って作成することができる：

データ構造 ds についての情報：

アプリケーション  (1)

半順序集合の最小値  (1)

"Deque"は，半順序集合の最小値を計算するのに便利である．半順序集合は，要素が順序の関係を持たない場合にIndeterminateを返すことができる順序関数を必要とする．

以下は，順序関数について集合の最小値を返すか，最小値がない場合にIndeterminateを返すかする：

この順序関数はDivisibleを使う．つまり，数が互いで割り切れない場合には，Indeterminateの結果を返す：

4も6も2で割り切れるので，2が最小値である：

ここでは他の値に割り切ることができる数がないので，Indeterminateの結果が返される：