LeetCode 641: Diseño circular Deque
Estoy publicando una solución para el "Design Circular Deque" de LeetCode. Si desea revisarlo, hágalo. ¡Gracias!
Problema
Diseñe su implementación de la cola circular de dos extremos (deque).
Su implementación debe admitir las siguientes operaciones:
MyCircularDeque(k): Constructor, establezca el tamaño de la deque en k.insertFront(): Agrega un elemento al frente de Deque. Devuelve verdadero si la operación se realiza correctamente.insertLast(): Agrega un elemento en la parte posterior de Deque. Devuelve verdadero si la operación se realiza correctamente.deleteFront(): Elimina un elemento del frente de Deque. Devuelve verdadero si la operación se realiza correctamente.deleteLast(): Elimina un elemento de la parte posterior de Deque. Devuelve verdadero si la operación se realiza correctamente.getFront(): Obtiene el elemento frontal del Deque. Si el deque está vacío, devuelve -1.getRear(): Obtiene el último elemento de Deque. Si el deque está vacío, devuelve -1.isEmpty(): Comprueba si Deque está vacío o no.isFull(): Comprueba si Deque está lleno o no.
Ejemplo:
MyCircularDeque circularDeque = new MycircularDeque(3); // set the size to be 3
circularDeque.insertLast(1); // return true
circularDeque.insertLast(2); // return true
circularDeque.insertFront(3); // return true
circularDeque.insertFront(4); // return false, the queue is full
circularDeque.getRear(); // return 2
circularDeque.isFull(); // return true
circularDeque.deleteLast(); // return true
circularDeque.insertFront(4); // return true
circularDeque.getFront(); // return 4
Nota:
- Todos los valores estarán en el rango de [0, 1000].
- El número de operaciones estará en el rango de [1, 1000].
- No utilice la biblioteca Deque incorporada.
Código:
// The following block might slightly improve the execution time;
// Can be removed;
static const auto __optimize__ = []() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cout.tie(nullptr);
return 0;
}();
// Most of headers are already included;
// Can be removed;
#include <cstdint>
#include <vector>
struct MyCircularDeque {
MyCircularDeque(int k): stream(k, 0), counts(0), k(k), head(k - 1), tail(0) {}
const bool insertFront(
const int value
) {
if (isFull()) {
return false;
}
stream[head] = value;
--head;
head += k;
head %= k;
++counts;
return true;
}
const bool insertLast(const int value) {
if (isFull()) {
return false;
}
stream[tail] = value;
++tail;
tail %= k;
++counts;
return true;
}
const bool deleteFront() {
if (isEmpty()) {
return false;
}
++head;
head %= k;
--counts;
return true;
}
const bool deleteLast() {
if (isEmpty()) {
return false;
}
--tail;
tail += k;
tail %= k;
--counts;
return true;
}
const int getFront() {
return isEmpty() ? -1 : stream[(head + 1) % k];
}
const int getRear() {
return isEmpty() ? -1 : stream[(tail - 1 + k) % k];
}
const bool isEmpty() {
return !counts;
}
const bool isFull() {
return counts == k;
}
private:
using ValueType = std::uint_fast16_t;
std::vector<ValueType> stream;
ValueType counts;
ValueType k;
ValueType head;
ValueType tail;
};
Respuestas
Usar el mismo tipo para el contenido de deque y los tamaños / índices (
k, count, head, tail) se siente mal. Al menos,kycountdebería serlostd::vector::size_type.Ya que estás retrocediendo con el deque
std::vector, haciendoheadytailelstd::vector::iteratoraspecto más idiomático.kno es el nombre más descriptivo. Considerecapacity.No estoy seguro de que
std::vectorsea el mejor contenedor para hacer una copia de seguridad de la deque de tamaño fijo. Después de todo, el objetivostd::vectores tener un tamaño dinámico.std::array, o incluso una simple matriz de estilo C antiguo, se ve más natural.
Puede llamar stream.reserve(k)al constructor para mejorar la eficiencia del vector porque sabe que solo tendrá kelementos, por .reserve()lo que preasignará la memoria.
Preferir usar std::size_toverint
int k seríastd::size_t k
No ha declarado un constructor de copia ni un operador de asignación de copia . Esto puede causar problemas si desea asignar uno Dequea otro.
Inlining algunas funciones miembro de su structparecido isEmpty(), getRear(), getFront() puede mejorar el rendimiento de su contenedor, pero será un cambio por el espacio.
Si está haciendo esto con el único propósito de completar el desafío, puede ignorar la siguiente parte
Plantillas
En este momento, dequeestá obligado a usar std::uint_fast16_t. Pero, ¿y si quisiera hacer una serie dequede nombres? ¿O uno dequede diferentes valores decimales? No puedo crear simplemente 15 clases para cada uno de los tipos de datos.
Por lo tanto, usaré plantillas en C ++ para poder crear un archivo deque .
La sintaxis es simple
template < typename T >
struct deque
{
public:
// public member functions
private:
std::vector< T > stream;
};
Ahora, cuando desee crear una nueva deque, puede hacerlo deque<any_data_type> my_deque.
Dondequiera que lo use ValueType, lo reemplaza con T.
Lo que hace C ++ es que toma any_data_typey reemplaza Tcon ese tipo de datos durante el tiempo de compilación . La implementación de esto en su programa le enseñará mucho sobre cómo funcionan las plantillas en C ++, lo que será útil en sus proyectos futuros.
Plantillas en C ++
Creo que este es un tema para su código:, constdonde lo puso, no tiene ningún beneficio; y falta en otros lugares donde debería estar allí. Cada función MyCircularDequedebe eliminarse al constprincipio, porque esos valores de retorno son escalares, por lo que marcarlos no consttiene literalmente ningún efecto. insertLast(const int value)tiene un efecto ligeramente mayor, pero en realidad no es importante.
El lugar más importante para colocar constes modificar la consistencia de thissus métodos gety is. Deben haber constagregado después del paréntesis. Esto registra una promesa de que los métodos no modifican ningún miembro.