Deque

import { Deque } from "jsr:@ende/data-structures";

class

class Deque<T> implements Iterable<T>, ReadonlyDeque<T>

A double-ended queue backed by a ring buffer. Pushing, popping, and indexed access stay fast as the deque grows.

Method	Average Case	Worst Case
pushBack()	O(1)	O(n) amort.
pushFront()	O(1)	O(n) amort.
popBack()	O(1)	O(1)
popFront()	O(1)	O(1)
peekFront()	O(1)	O(1)
peekBack()	O(1)	O(1)
at()	O(1)	O(1)
isEmpty()	O(1)	O(1)
clear()	O(1)	O(1)
removeAt()	O(n)	O(n)
removeFirst()	O(n)	O(n)
includes()	O(n)	O(n)
find()	O(n)	O(n)
findIndex()	O(n)	O(n)
retain()	O(n)	O(n)
toArray()	O(n)	O(n)
Deque.from()	O(n)	O(n)

Example: Usage

import { Deque } from "@ende/data-structures/deque";
import { assertEquals } from "@ende/assert";

const deque = new Deque<number>();
deque.pushBack(1, 2, 3);
assertEquals(deque.popFront(), 1);
assertEquals(deque.length, 2);
assertEquals([...deque], [2, 3]);

Constructors

`constructor`

new Deque(source?: Iterable<T>)

Creates an empty deque, optionally populated from an iterable.

source?: Iterable<T>: An optional iterable to populate the deque.

Example: Creating an empty deque

import { Deque } from "@ende/data-structures/deque";
import { assertEquals } from "@ende/assert";

const deque = new Deque<number>();
assertEquals(deque.length, 0);

Example: Creating a deque from an iterable

import { Deque } from "@ende/data-structures/deque";
import { assertEquals } from "@ende/assert";

const deque = new Deque([1, 2, 3]);
assertEquals([...deque], [1, 2, 3]);

Static methods

`from`

static from<T>(collection: ArrayLike<T> | Iterable<T> | Deque<T>): Deque<T>

Create a new deque from an array-like, iterable, or existing deque.

collection: ArrayLike<T> | Iterable<T> | Deque<T>: An array-like, iterable, or existing deque.

Returns

A new deque containing the values from the collection.

Example: Creating a deque from an array

import { Deque } from "@ende/data-structures/deque";
import { assertEquals } from "@ende/assert";

const deque = Deque.from([1, 2, 3]);
assertEquals([...deque], [1, 2, 3]);

Example: Creating a deque from an existing deque

import { Deque } from "@ende/data-structures/deque";
import { assertEquals } from "@ende/assert";

const original = new Deque([1, 2, 3]);
const copy = Deque.from(original);
assertEquals([...copy], [1, 2, 3]);

static from<T, U, V = undefined>(collection: ArrayLike<T> | Iterable<T> | Deque<T>, options: { map: (value: T, index: number) => U; thisArg?: V }): Deque<U>

Create a new deque from an array-like, iterable, or existing deque, with a mapping function applied to each element.

collection: ArrayLike<T> | Iterable<T> | Deque<T>: An array-like, iterable, or existing deque.
options: { map: (value: T, index: number) => U; thisArg?: V }: Options with a map function and optional thisArg.

Returns

A new deque containing the mapped values from the collection.

Example: Creating a deque with a mapping function

import { Deque } from "@ende/data-structures/deque";
import { assertEquals } from "@ende/assert";

const deque = Deque.from([1, 2, 3], { map: (v) => v * 10 });
assertEquals([...deque], [10, 20, 30]);

static from<T, U, V>(collection: ArrayLike<T> | Iterable<T> | Deque<T>, options?: { map?: (value: T, index: number) => U; thisArg?: V }): Deque<U>

Properties

`[Symbol.toStringTag]`

readonly [Symbol.toStringTag]: "Deque"

The string tag used by Object.prototype.toString.

Example: Usage

import { Deque } from "@ende/data-structures/deque";
import { assertEquals } from "@ende/assert";

const deque = new Deque<number>();
assertEquals(deque[Symbol.toStringTag], "Deque");

Methods

`length`

get length(): number

The number of elements in the deque.

Returns

The number of elements in the deque.

Example: Getting the length

import { Deque } from "@ende/data-structures/deque";
import { assertEquals } from "@ende/assert";

const deque = new Deque([1, 2, 3]);
assertEquals(deque.length, 3);

`isEmpty`

isEmpty(): boolean

Checks if the deque contains no elements.

Returns

true if the deque is empty, otherwise false.

Example: Checking if the deque is empty

import { Deque } from "@ende/data-structures/deque";
import { assertEquals } from "@ende/assert";

const deque = new Deque<number>();
assertEquals(deque.isEmpty(), true);

deque.pushBack(1);
assertEquals(deque.isEmpty(), false);

`pushBack`

pushBack(value: T, ...rest: T[]): number

Append one or more values to the back of the deque.

value: T: The first value to append.
...rest: T[]: Additional values to append.

Returns

The new length of the deque.

Example: Pushing values to the back

import { Deque } from "@ende/data-structures/deque";
import { assertEquals } from "@ende/assert";

const deque = new Deque<number>();
deque.pushBack(1, 2, 3);
assertEquals([...deque], [1, 2, 3]);

`pushFront`

pushFront(value: T, ...rest: T[]): number

Prepend one or more values to the front of the deque. Values are inserted in argument order, so pushFront(1, 2, 3) results in front-to-back order [1, 2, 3, ...existing].

value: T: The first value to prepend.
...rest: T[]: Additional values to prepend.

Returns

The new length of the deque.

Example: Pushing values to the front

import { Deque } from "@ende/data-structures/deque";
import { assertEquals } from "@ende/assert";

const deque = new Deque([4, 5]);
deque.pushFront(1, 2, 3);
assertEquals([...deque], [1, 2, 3, 4, 5]);

`popBack`

popBack(): T | undefined

Remove and return the back element, or undefined if the deque is empty.

Returns

The back element, or undefined if empty.

Example: Popping from the back

import { Deque } from "@ende/data-structures/deque";
import { assertEquals } from "@ende/assert";

const deque = new Deque([1, 2, 3]);
assertEquals(deque.popBack(), 3);
assertEquals([...deque], [1, 2]);

`popFront`

popFront(): T | undefined

Remove and return the front element, or undefined if the deque is empty.

Returns

The front element, or undefined if empty.

Example: Popping from the front

import { Deque } from "@ende/data-structures/deque";
import { assertEquals } from "@ende/assert";

const deque = new Deque([1, 2, 3]);
assertEquals(deque.popFront(), 1);
assertEquals([...deque], [2, 3]);

`removeFirst`

removeFirst(predicate: (value: T, index: number) => boolean): T | undefined

Remove and return the first element matching the predicate, scanning from front to back. The gap is closed by shifting whichever side (front or back) has fewer elements to move, so removals near either end are fast.

predicate: (value: T, index: number) => boolean: A function called for each element with its index. The first element for which it returns true is removed and returned.

Returns

The removed element, or undefined if no match was found.

Example: Removing the first even number

import { Deque } from "@ende/data-structures/deque";
import { assertEquals } from "@ende/assert";

const deque = new Deque([1, 2, 3, 4]);
assertEquals(deque.removeFirst((v) => v % 2 === 0), 2);
assertEquals([...deque], [1, 3, 4]);

`removeAt`

removeAt(index: number): T | undefined

Remove and return the element at the given index (0-based from front). Negative indices count from the back (-1 is the last element). Returns undefined for out-of-range indices. The gap is closed by shifting whichever side (front or back) has fewer elements to move.

index: number: The zero-based index. Negative values count from the back.

Returns

The removed element, or undefined if the index is out of range.

Example: Removing by index

import { Deque } from "@ende/data-structures/deque";
import { assertEquals } from "@ende/assert";

const deque = new Deque([10, 20, 30, 40]);
assertEquals(deque.removeAt(1), 20);
assertEquals([...deque], [10, 30, 40]);

Example: Removing with a negative index

import { Deque } from "@ende/data-structures/deque";
import { assertEquals } from "@ende/assert";

const deque = new Deque([10, 20, 30, 40]);
assertEquals(deque.removeAt(-1), 40);
assertEquals([...deque], [10, 20, 30]);

`find`

find(predicate: (value: T, index: number) => boolean): T | undefined

Return the first element matching the predicate, scanning from front to back, without removing it. Returns undefined if no match is found.

predicate: (value: T, index: number) => boolean: A function called for each element with its index. The first element for which it returns true is returned.

Returns

The first matching element, or undefined if no match was found.

Example: Finding the first even number

import { Deque } from "@ende/data-structures/deque";
import { assertEquals } from "@ende/assert";

const deque = new Deque([1, 2, 3, 4]);
assertEquals(deque.find((v) => v % 2 === 0), 2);
assertEquals(deque.find((v) => v > 10), undefined);

`findIndex`

findIndex(predicate: (value: T, index: number) => boolean): number

Return the index of the first element matching the predicate, scanning from front to back. Returns -1 if no match is found.

predicate: (value: T, index: number) => boolean: A function called for each element with its index. The index of the first element for which it returns true is returned.

Returns

The index of the first matching element, or -1 if not found.

Example: Finding the index of the first even number

import { Deque } from "@ende/data-structures/deque";
import { assertEquals } from "@ende/assert";

const deque = new Deque([1, 2, 3, 4]);
assertEquals(deque.findIndex((v) => v % 2 === 0), 1);
assertEquals(deque.findIndex((v) => v > 10), -1);

`peekFront`

peekFront(): T | undefined

Return the front element without removing it, or undefined if the deque is empty.

Returns

The front element, or undefined if empty.

Example: Peeking at the front

import { Deque } from "@ende/data-structures/deque";
import { assertEquals } from "@ende/assert";

const deque = new Deque([1, 2, 3]);
assertEquals(deque.peekFront(), 1);
assertEquals(deque.length, 3);

`peekBack`

peekBack(): T | undefined

Return the back element without removing it, or undefined if the deque is empty.

Returns

The back element, or undefined if empty.

Example: Peeking at the back

import { Deque } from "@ende/data-structures/deque";
import { assertEquals } from "@ende/assert";

const deque = new Deque([1, 2, 3]);
assertEquals(deque.peekBack(), 3);
assertEquals(deque.length, 3);

`at`

at(index: number): T | undefined

Return the element at the given index (0-based from front). Negative indices count from the back (-1 is the last element). Returns undefined for out-of-range indices.

index: number: The zero-based index. Negative values count from the back.

Returns

The element at the index, or undefined if out of range.

Example: Accessing elements by index

import { Deque } from "@ende/data-structures/deque";
import { assertEquals } from "@ende/assert";

const deque = new Deque([10, 20, 30, 40]);
assertEquals(deque.at(0), 10);
assertEquals(deque.at(-1), 40);
assertEquals(deque.at(99), undefined);

`includes`

includes(value: T): boolean

Check whether the deque contains a value, using SameValueZero comparison (like Array.prototype.includes).

value: T: The value to search for.

Returns

true if the deque contains the value, otherwise false.

Example: Checking for membership

import { Deque } from "@ende/data-structures/deque";
import { assertEquals } from "@ende/assert";

const deque = new Deque([1, 2, 3]);
assertEquals(deque.includes(2), true);
assertEquals(deque.includes(99), false);

Example: NaN is found (SameValueZero semantics)

import { Deque } from "@ende/data-structures/deque";
import { assertEquals } from "@ende/assert";

const deque = new Deque([1, NaN, 3]);
assertEquals(deque.includes(NaN), true);

`clear`

clear(): void

Remove all elements and release the backing buffer.

Example: Clearing the deque

import { Deque } from "@ende/data-structures/deque";
import { assertEquals } from "@ende/assert";

const deque = new Deque([1, 2, 3]);
deque.clear();
assertEquals(deque.length, 0);
assertEquals(deque.isEmpty(), true);

`retain`

retain(predicate: (value: T, index: number) => boolean): void

Keep only the elements for which the predicate returns true, removing the rest in place. Equivalent to an in-place Array.prototype.filter. The predicate is called once per element in front-to-back order.

predicate: (value: T, index: number) => boolean: A function called for each element with its index. Elements for which it returns false are removed.

Example: Retaining only odd numbers

import { Deque } from "@ende/data-structures/deque";
import { assertEquals } from "@ende/assert";

const deque = new Deque([1, 2, 3, 4, 5]);
deque.retain((v) => v % 2 !== 0);
assertEquals([...deque], [1, 3, 5]);

`toArray`

toArray(): T[]

Return a shallow copy of the deque's contents as an array, in front-to-back order.

Returns

An array containing the deque's elements in order.

Example: Converting to an array

import { Deque } from "@ende/data-structures/deque";
import { assertEquals } from "@ende/assert";

const deque = new Deque([1, 2, 3]);
assertEquals(deque.toArray(), [1, 2, 3]);

`[Symbol.iterator]`

[Symbol.iterator](): IterableIterator<T>

Iterate over the deque's elements from front to back. Non-destructive (unlike BinaryHeap).

Returns

An iterator yielding elements from front to back.

Example: Iterating over the deque

import { Deque } from "@ende/data-structures/deque";
import { assertEquals } from "@ende/assert";

const deque = new Deque([1, 2, 3]);
assertEquals([...deque], [1, 2, 3]);

`reversed`

reversed(): IterableIterator<T>

Iterate over the deque's elements from back to front.

Returns

An iterator yielding elements from back to front.

Example: Iterating in reverse

import { Deque } from "@ende/data-structures/deque";
import { assertEquals } from "@ende/assert";

const deque = new Deque([1, 2, 3]);
assertEquals([...deque.reversed()], [3, 2, 1]);

Source