Skip to content

Deque ​

Deque<T> implements a double-ended queue with amortized O(1) insertion and removal at both ends.

Construction ​

SyntaxDescription
Deque<T>()Create a new empty deque

The type parameter T determines the element type. T can be a scalar value type (boolean, char, integer, or float); heap-owned values such as string are not supported.

Methods ​

MethodSignatureReturnsDescription
pushFront(T) => voidvoidAdd an element to the front
pushBack(T) => voidvoidAdd an element to the back
popFront() => T?T?Remove and return the front element, or empty if empty
popBack() => T?T?Remove and return the back element, or empty if empty
peekFront() => T?T?Return the front element without removing it, or empty if empty
peekBack() => T?T?Return the back element without removing it, or empty if empty
len() => usizeusizeNumber of elements
isEmpty() => booleanbooleanWhether the deque has no elements
clear() => voidvoidRemove all elements

popFront, popBack, peekFront, and peekBack return T?, call with a presence check or default value.

The native handle is released automatically when the binding goes out of scope.

Complexity ​

OperationTime Complexity
pushFrontO(1)
pushBackAmortized O(1)
popFrontO(1)
popBackO(1)
peekFrontO(1)
peekBackO(1)
lenO(1)
isEmptyO(1)
clearO(1)

Examples ​

Construction ​

tyrus
import { Deque } from "tyrus:algorithm";

const dq = Deque<i32>();

pushFront and pushBack ​

tyrus
const dq = Deque<i32>();

dq.pushBack(2);
dq.pushBack(3);
dq.pushFront(1);

print(dq.len());  // 3

popFront ​

tyrus
const dq = Deque<i32>();

dq.pushBack(1);
dq.pushBack(2);
dq.pushBack(3);

const p1: i32? = dq.popFront();
if (p1) {
    print(p1);  // 1
}

const p2: i32? = dq.popFront();
if (p2) {
    print(p2);  // 2
}

const p3: i32? = dq.popFront();
if (p3) {
    print(p3);  // 3
}

const p4: i32? = dq.popFront();
print(p4 ?? -1);  // -1

popBack ​

tyrus
const dq = Deque<i32>();

dq.pushBack(1);
dq.pushBack(2);
dq.pushBack(3);

const p1: i32? = dq.popBack();
if (p1) {
    print(p1);  // 3
}

const p2: i32? = dq.popBack();
if (p2) {
    print(p2);  // 2
}

const p3: i32? = dq.popBack();
if (p3) {
    print(p3);  // 1
}

const p4: i32? = dq.popBack();
print(p4 ?? -1);  // -1

peekFront and peekBack ​

tyrus
const dq = Deque<i32>();

dq.pushBack(10);
dq.pushBack(20);

const f: i32? = dq.peekFront();
if (f) {
    print(f);  // 10
}

const b: i32? = dq.peekBack();
if (b) {
    print(b);  // 20
}

print(dq.len());  // 2

len ​

tyrus
const dq = Deque<i32>();

print(dq.len());  // 0

dq.pushBack(1);
dq.pushFront(2);

print(dq.len());  // 2

isEmpty ​

tyrus
const dq = Deque<i32>();

print(dq.isEmpty());  // true

dq.pushBack(1);

print(dq.isEmpty());  // false

clear ​

tyrus
const dq = Deque<i32>();

dq.pushBack(1);
dq.pushBack(2);
dq.pushBack(3);

print(dq.len());  // 3

dq.clear();

print(dq.isEmpty());  // true
print(dq.len());      // 0

Mixed pushFront and popBack (queue behavior) ​

tyrus
const dq = Deque<i32>();

dq.pushBack(1);
dq.pushBack(2);
dq.pushFront(0);

const p1: i32? = dq.popBack();
if (p1) {
    print(p1);  // 2
}

const p2: i32? = dq.popFront();
if (p2) {
    print(p2);  // 0
}

const p3: i32? = dq.popBack();
if (p3) {
    print(p3);  // 1
}

print(dq.isEmpty());  // true