Deque
Deque<T> implementa una cola de doble extremo con inserción y eliminación O(1) amortizada en ambos extremos.
Construcción
| Sintaxis | Descripción |
|---|---|
Deque<T>() | Crea un nuevo deque vacío |
El parámetro de tipo T determina el tipo del elemento. T puede ser un valor escalar (boolean, char, entero o float); los valores con propiedad en el heap, como string, no son compatibles.
Métodos
| Método | Firma | Retorna | Descripción |
|---|---|---|---|
pushFront | (T) => void | void | Agrega un elemento al frente |
pushBack | (T) => void | void | Agrega un elemento al final |
popFront | () => T? | T? | Elimina y retorna el elemento del frente, o vacío si está vacío |
popBack | () => T? | T? | Elimina y retorna el elemento del final, o vacío si está vacío |
peekFront | () => T? | T? | Retorna el elemento del frente sin eliminar, o vacío si está vacío |
peekBack | () => T? | T? | Retorna el elemento del final sin eliminar, o vacío si está vacío |
len | () => usize | usize | Número de elementos |
isEmpty | () => boolean | boolean | Si el deque no tiene elementos |
clear | () => void | void | Elimina todos los elementos |
popFront, popBack, peekFront y peekBack retornan T?, llame con verificación de presencia o valor por defecto.
El handle nativo se libera automáticamente cuando la variable sale del ámbito.
Complejidad
| Operación | Complejidad 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) |
Ejemplos
Construcción
tyrus
import { Deque } from "tyrus:algorithm";
const dq = Deque<i32>();pushFront y 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 y 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 y popBack mixtos (comportamiento de cola)
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