WOLFRAM

Wolfram 语言与系统参考资料中心

"Deque" （数据结构）

"Deque"

表示可以从前端和后端添加或删除的表达式队列.

更多信息

  • 双端队列是元素的集合，这些元素支持按先进先出和后进先出方式插入和移除：
  • CreateDataStructure["Deque"]创建新的空的 "Deque"
    Typed[x,"Deque"]指定 x 的类型为 "Deque"
    Typed[x,"Deque"]将类型 "Deque" 赋予 x
  • 对于类型为 "Deque" 的数据结构，可进行以下操作：
  • ds["Copy"]返回 ds 的副本时间：O(n)
    ds["DropAll"]丢弃 ds 中的所有元素时间：O(n)
    ds["Elements"]返回 ds 的元素列表时间：O(n)
    ds["EmptyQ"]如果 ds 为空则为 True时间：O(1)
    ds["Fold",fun,init]对由 init 开始的 ds 的元素应用 fun，并累计结果时间：O(n)
    ds["Length"]ds 中元素的数量时间：O(1)
    ds["PeekBack"]ds 中最后一个元素时间：O(1)
    ds["PeekFront"]ds 中第一个元素时间：O(1)
    ds["PopBack"]移除 ds 中最后一个元素并返回该元素时间：O(1)
    ds["PopFront"]移除 ds 中第一个元素并返回该元素时间：O(1)
    ds["PushBack",x]将 x 添加到 ds 的末尾时间：O(1)
    ds["PushBackList",elems]将 elems 添加到 ds 的末尾时间：O(nelems)
    ds["PushFront",x]将 x 添加到 ds 的前面时间：O(1)
    ds["PushFrontList",elems]将 elems 添加到 ds 前端时间：O(nelems)
    ds["Visualization"]返回 ds 的可视化时间：O(n)
  • 还支持以下函数：
  • dsi===dsj如果 dsi 等于 dsj 则为 True
    FullForm[ds]ds 的完全形式
    Information[ds]关于 ds 的信息
    InputForm[ds]ds 的输入形式
    Normal[ds]将 ds 转换成普通表达式

范例

打开所有单元 关闭所有单元

基本范例  (2)

可用 CreateDataStructure 创建新的 "Deque"：

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"]

它有一个元素：

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)

可用 CreateDataStructure 创建新的 "Deque"：

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

关于数据结构 ds 的信息：

Wolfram Language code: Information[ds]

应用  (1)

部分有序集合的最小值  (1)

"Deque" 对于计算部分有序集合 (partially ordered set) 的最小值非常有用. 部分有序集合需要一个排序函数，如果元素之间没有顺序关系，则该函数返回 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]

2 可以被 4 和 6 整除，所以它是最小值：

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

这里没有可以被彼此整除的数字；所以结果为 Indeterminate：

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