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

ds 被初始化为空：

往 ds 中添加一个元素：

ds 不再为空：

它有一个元素：

再添加另一个元素并查看. 下面显示第一个元素：

移除最后一个元素并返回该元素：

返回表达式形式的 ds：

可快速地将元素放入队列：

可以生成数据结构的可视化：

将所有元素相加：

范围  (1)

信息  (1)

可用 CreateDataStructure 创建新的 "Deque"：

关于数据结构 ds 的信息：

应用  (1)

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

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

下面的程序返回排序后集合的最小值，如果没有最小值，则返回 Indeterminate：

排序函数使用了 Divisible；如果数字不能被彼此整除，则结果为 Indeterminate：

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

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