WOLFRAM

Wolfram言語 ＆ システムドキュメントセンター

"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を使って作成できる：

Wolfram Language code: ds = CreateDataStructure["Deque"]

ds は最初は空である：

Wolfram Language code: ds["EmptyQ"]

ds に要素を加える：

Wolfram Language code: ds["PushBack", f[1]]

ds はもはや空ではない：

Wolfram Language code: ds["EmptyQ"]

要素を1個含む：

Wolfram Language code: ds["Length"]

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

Wolfram Language code: ds["PushFront", f[2]]; ds["PeekBack"]

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

Wolfram Language code: ds["PopBack"]

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

Wolfram Language code: Normal[ds]

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

Wolfram Language code: ds = CreateDataStructure["Deque"]; Do[ds["PushBack", i], {i, 1000}]

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

Wolfram Language code: ds["Visualization"]

全要素を合計する：

Wolfram Language code: ds["Fold", Plus, 0]

スコープ  (1)

情報  (1)

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

Wolfram Language code: ds = CreateDataStructure["Deque"]

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

Wolfram Language code: Information[ds]

アプリケーション  (1)

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

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

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

Wolfram Language code: PartialMinimum[data_List, orderFun_] := Module[{list, len}, list = Range[Length[data]]; While[Length[list] > 1, len = Length[list]; list = PartialMinimumWorker[data, list, orderFun]; If[Length[list] === len, Return[Indeterminate]]]; data[[First[list]]]]
Wolfram Language code: PartialMinimumWorker[data_, curr_, orderFun_] := Module[{work, min, exchange = False}, work = CreateDataStructure["Deque"]; min = Fold[Function[{currVal, newVal}, Module[{d1, d2}, d1 = Part[data, currVal]; d2 = Part[data, newVal]; Switch[orderFun[d1, d2], 0, currVal, 1, currVal, -1, exchange = True;newVal, _, work["PushBack", newVal];currVal]]], curr]; If[exchange, work["PushFront", min], work["PushBack", min]]; Normal[work]]

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

Wolfram Language code: order[x_, y_] := Which[Divisible[x, y], -1, Divisible[y, x], 1, True, Indeterminate]

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

Wolfram Language code: PartialMinimum[{2, 4, 6}, order]

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

Wolfram Language code: PartialMinimum[{2, 4, 3}, order]