Skip to content

Deque ​

Deque<T> implementa uma fila de duas pontas com inserção e remoção O(1) amortizado em ambas as extremidades.

Construção ​

SintaxeDescrição
Deque<T>()Cria um novo deque vazio

O parâmetro de tipo T determina o tipo do elemento. T pode ser um valor escalar (boolean, char, inteiro ou float); valores com posse no heap, como string, não são aceitos.

Métodos ​

MétodoAssinaturaRetornaDescrição
pushFront(T) => voidvoidAdiciona um elemento na frente
pushBack(T) => voidvoidAdiciona um elemento no final
popFront() => T?T?Remove e retorna o elemento da frente, ou vazio se vazio
popBack() => T?T?Remove e retorna o elemento do final, ou vazio se vazio
peekFront() => T?T?Retorna o elemento da frente sem remover, ou vazio se vazio
peekBack() => T?T?Retorna o elemento do final sem remover, ou vazio se vazio
len() => usizeusizeNúmero de elementos
isEmpty() => booleanbooleanSe o deque não tem elementos
clear() => voidvoidRemove todos os elementos

popFront, popBack, peekFront e peekBack retornam T?, chame com verificação de presença ou valor padrão.

O handle nativo é liberado automaticamente quando a variável sai de escopo.

Complexidade ​

OperaçãoComplexidade Temporal
pushFrontO(1)
pushBackAmortizado O(1)
popFrontO(1)
popBackO(1)
peekFrontO(1)
peekBackO(1)
lenO(1)
isEmptyO(1)
clearO(1)

Exemplos ​

Construção ​

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

const dq = Deque<i32>();

pushFront e 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 e 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

pushFront e popBack misturados (comportamento de fila) ​

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