Deque
Deque<T> implementa uma fila de duas pontas com inserção e remoção O(1) amortizado em ambas as extremidades.
Construção
| Sintaxe | Descriçã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étodo | Assinatura | Retorna | Descrição |
|---|---|---|---|
pushFront | (T) => void | void | Adiciona um elemento na frente |
pushBack | (T) => void | void | Adiciona 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 | () => usize | usize | Número de elementos |
isEmpty | () => boolean | boolean | Se o deque não tem elementos |
clear | () => void | void | Remove 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ção | Complexidade Temporal |
|---|---|
pushFront | O(1) |
pushBack | Amortizado O(1) |
popFront | O(1) |
popBack | O(1) |
peekFront | O(1) |
peekBack | O(1) |
len | O(1) |
isEmpty | O(1) |
clear | O(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()); // 3popFront
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); // -1popBack
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); // -1peekFront 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()); // 2len
tyrus
const dq = Deque<i32>();
print(dq.len()); // 0
dq.pushBack(1);
dq.pushFront(2);
print(dq.len()); // 2isEmpty
tyrus
const dq = Deque<i32>();
print(dq.isEmpty()); // true
dq.pushBack(1);
print(dq.isEmpty()); // falseclear
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()); // 0pushFront 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