WOLFRAM

Wolfram Language & System Documentation Center

"Deque" (Data Structure)

"Deque"

represents a queue of expressions that can be added or removed from the front and back.

Details

  • A deque is a collection of elements that supports both first-in, first-out and last-in, first-out insertion and removal:
  • CreateDataStructure["Deque"]create a new empty "Deque"
    CreateDataStructure["Deque",elems]create a new "Deque" containing elems
    Typed[x,"Deque"]give x the type "Deque"
  • For a data structure of type "Deque", the following operations can be used:
  • ds["Copy"]return a copy of dstime: O(n)
    ds["DropAll"]drop all the elements from dstime: O(n)
    ds["Elements"]return a list of the elements of dstime: O(n)
    ds["EmptyQ"]True, if the ds is emptytime: O(1)
    ds["Fold",fun,init]apply fun to the elements of ds, starting with init, accumulating a resulttime: O(n)
    ds["Length"]number of elements in dstime: O(1)
    ds["PeekBack"]the last element in dstime: O(1)
    ds["PeekFront"]the first element in dstime: O(1)
    ds["PopBack"]remove the last element in ds and return ittime: O(1)
    ds["PopFront"]remove the first element in ds and return ittime: O(1)
    ds["PushBack",x]add x to the end of dstime: O(1)
    ds["PushBackList",elems]add elems to the end of dstime: O(nelems)
    ds["PushFront",x]add x to the front of dstime: O(1)
    ds["PushFrontList",elems]add elems to the front of dstime: O(nelems)
    ds["Visualization"]return a visualization of dstime: O(n)
  • The following functions are also supported:
  • dsi===dsjTrue, if dsi equals dsj
    FullForm[ds]full form of ds
    Information[ds]information about ds
    InputForm[ds]input form of ds
    Normal[ds]convert ds to a normal expression

Examples

open all close all

Basic Examples  (2)

A new "Deque" can be created with CreateDataStructure:

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

ds is initially empty:

Wolfram Language code: ds["EmptyQ"]

Add an element to ds:

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

ds is no longer empty:

Wolfram Language code: ds["EmptyQ"]

It has one element:

Wolfram Language code: ds["Length"]

Add another element and peek. This shows the first element:

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

Remove the last element and return it:

Wolfram Language code: ds["PopBack"]

Return an expression version of ds:

Wolfram Language code: Normal[ds]

It is fast to put elements into a queue:

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

A visualization of the data structure can be generated:

Wolfram Language code: ds["Visualization"]

Sum all the elements:

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

Scope  (1)

Information  (1)

A new "Deque" can be created with CreateDataStructure:

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

Information about the data structure ds:

Wolfram Language code: Information[ds]

Applications  (1)

Minimum of a Partially Ordered Set  (1)

A "Deque" is useful for computing the minimum of a partially ordered set. A partially ordered set needs an ordering function that can return Indeterminate if the elements do not have an ordering relation.

This returns the minimum of a set for the ordering function or Indeterminate if there is no minimum value:

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

This ordering function uses Divisible; if the numbers are not divisible by each other, the result is Indeterminate:

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

2 can be divided into both 4 and 6, so it is the minimum value:

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

There is no number here that can be divided into the others; the result is Indeterminate:

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