La tarea es implementar un Deque dinámico utilizando una clase de plantillas y una array circular , que tenga las siguientes funcionalidades:
- front(): obtiene el elemento frontal de la deque.
- back(): Obtener el último elemento de la deque.
- push_back(X): Empuje X al final de la deque.
- push_front (X): Presione X al comienzo de la deque.
- pop_front(): Elimina un elemento desde el inicio de la deque.
- pop_back(): elimina un elemento del final de la deque
- vacío(): comprueba si deque está vacío o no
- capacidad(): número máximo actual de elementos que deque puede almacenar
- size(): Número de elementos en el deque
A continuación se muestra la ilustración paso a paso:
- Inicialmente, el deque está vacío.
- Inserte 1 en la parte posterior de deque
- Inserte los elementos 2, 3 en la parte posterior de deque
- Insertar 4 al frente de deque
- Inserte 5 en la parte posterior de deque
- Pop 2 elementos desde el frente y 2 elementos desde la parte posterior de deque
- Pop 1 elemento desde el frente de deque
Enfoque: la idea es duplicar el tamaño de la array utilizada cada vez que la capacidad de la array se llena y copiar los elementos de la array anterior en la nueva array. Siga los pasos a continuación para resolver el problema:
- Inicialice 4 variables, digamos frontIndex , backIndex , sizeVar y capacityVar , y una array, digamos arr[] para implementar el deque.
- Defina una función, digamos capacidad(), para encontrar el tamaño de la array actual utilizada y devolver el valor de la variable, variable de capacidad .
- Defina una función, digamos size(), para encontrar el recuento de elementos en la deque y devolver el valor de la variable, sizeVar.
- Defina una función diga full() para encontrar si el deque está lleno o no y devuelva verdadero si sizeVar es igual a capacityVar . De lo contrario, devuelve falso.
- Defina una función, diga vacío(), para encontrar si el deque está vacío o no y devuelva verdadero si frontIndex y backIndex son iguales a -1 . De lo contrario, devuelve falso.
- Defina una función, digamos Front(), para imprimir el elemento frontal de la deque . Si deque no está vacío(), imprima el elemento de arr[frontIndex] .
- Defina una función, diga Back() para imprimir el último elemento de la deque . Si deque no está vacío(), imprima el elemento de arr[BackIndex] .
- Defina una función, digamos push_back(X) para insertar un elemento al final de la deque:
- Si la deque está llena, duplique el tamaño de la array actual y copie los elementos de la array anterior en la nueva array.
- Si deque está vacío() , entonces asigne frontIndex = backIndex = 0 y luego asigne X tanto a arr[frontIndex] como a arr[backIndex] y luego incremente sizeVar en uno.
- De lo contrario, actualice backIndex como backIndex = (backIndex+1) %capacityVar y luego asigne X a arr[backIndex] e incremente sizeVar en uno.
- Defina una función, digamos push_front (X) para insertar un elemento al comienzo de la deque:
- Si la deque está llena, duplique el tamaño de la array actual y copie los elementos de la array anterior en la nueva array.
- Si deque está vacío() , entonces asigne frontIndex = backIndex = 0 y luego asigne X tanto a arr[frontIndex] como a arr[backIndex] y luego incremente sizeVar en uno.
- De lo contrario, actualice frontIndex como frontIndex = (frontIndex-1 + CapacityVar)%capacityVar y luego asigne X a arr[frontIndex] e incremente sizeVar en uno.
- Defina una función, digamos pop_front() para eliminar un elemento al frente de la deque:
- Si el deque está vacío, imprima «Underflow» .
- De lo contrario, si sizeVar es igual a 1, entonces asigne -1 a frontIndex y backIndex ambos y luego disminuya sizeVar en uno.
- De lo contrario, actualice frontIndex como frontIndex = (frontIndex+1)%capacityVar y disminuya sizeVar en uno.
- Defina una función, digamos pop_back() para eliminar un elemento al frente de la deque:
- Si el deque está vacío, imprima «Underflow» .
- De lo contrario, si sizeVar es igual a 1 , entonces asigne -1 a frontIndex y backIndex ambos y luego disminuya sizeVar en uno.
- De lo contrario, actualice backIndex como backIndex = (backndex-1 + capacityVar) %capacityVar y disminuya sizeVar en uno.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Class definition of the deque
template <class X>
class Deque {
private:
// Stores the frontIndex
int frontIndex;
// Stores the backIndex
int backIndex;
// Stores the array
X* arr;
// Stores the size of deque
int sizeVar;
// Stores the size of array
int capacityVar = 4;
public:
// Deque class constructor
Deque()
{
arr = new X[capacityVar];
frontIndex = backIndex = -1;
sizeVar = 0;
}
// Function methods
bool empty();
bool full();
void push_back(X x);
void push_front(X x);
void pop_front();
void pop_back();
X front();
X back();
int capacity();
int size();
};
// Function to find the capacity of the deque
template <class X>
int Deque<X>::capacity()
{
return capacityVar;
}
// Function to find the number of elements
// present in deque
template <class X>
int Deque<X>::size() { return sizeVar; }
// Function to check if deque is empty or not
template <class X>
bool Deque<X>::empty()
{
if (frontIndex == -1 && backIndex == -1)
return true;
else
return false;
}
// Function to check if deque is full or not
template <class X>
bool Deque<X>::full()
{
if (sizeVar == capacityVar)
return true;
else
return false;
}
// Function to find the front element of the deque
template <class X>
X Deque<X>::front()
{
// If deque is empty
if (empty()) {
cout << "Deque underflow" << endl;
abort();
}
return arr[frontIndex];
}
// Function to find the last element of the deque
template <class X>
X Deque<X>::back()
{
// If deque is empty
if (empty()) {
cout << "Deque underflow" << endl;
abort();
}
return arr[backIndex];
}
// Function to insert the element
// to the back of the deque
template <class X>
void Deque<X>::push_back(X x)
{
if (full()) {
// If the deque is full, then
// double the capacity
capacityVar = capacityVar * 2;
// Initialize new array of
// double size
X* temp = new X[capacityVar];
// Copy the elements of the
// previous array
int i = frontIndex;
int j = 0;
while (i != backIndex) {
temp[j] = arr[i];
i = (i + 1) % sizeVar;
j++;
}
temp[j] = arr[i];
frontIndex = 0;
backIndex = sizeVar - 1;
// Deallocate the memory
// of previous array
delete[] arr;
arr = temp;
}
// If size is zero
if (empty()) {
frontIndex = backIndex = 0;
arr[backIndex] = x;
sizeVar++;
return;
}
// Increment back index cyclically
backIndex = (backIndex + 1) % capacityVar;
arr[backIndex] = x;
sizeVar++;
return;
}
// Function to insert the element
// to the front of the deque
template <class X>
void Deque<X>::push_front(X x)
{
if (full()) {
// If the deque is full, then
// double the capacity
capacityVar = capacityVar * 2;
// Initialize new array of
// double size
X* temp = new X[capacityVar];
// Copy the elements of the
// previous array
int i = frontIndex;
int j = 0;
while (i != backIndex) {
temp[j] = arr[i];
i = (i + 1) % sizeVar;
j++;
}
temp[j] = arr[i];
frontIndex = 0;
backIndex = sizeVar - 1;
// Deallocate the memory
// of previous array
delete[] arr;
arr = temp;
}
// If size is zero
if (empty()) {
frontIndex = backIndex = 0;
arr[backIndex] = x;
sizeVar++;
return;
}
// Decrement front index cyclically
frontIndex
= (frontIndex - 1 + capacityVar) % capacityVar;
arr[frontIndex] = x;
sizeVar++;
return;
}
// Function to delete the element
// from the front of the deque
template <class X>
void Deque<X>::pop_front()
{
// If deque is empty
if (empty()) {
cout << "Deque underflow" << endl;
abort();
}
// If there is only one character
if (frontIndex == backIndex) {
// Mark deque as empty
// and decrement sizeVar
frontIndex = backIndex = -1;
sizeVar--;
return;
}
// Increment frontIndex cyclically
frontIndex = (frontIndex + 1) % capacityVar;
sizeVar--;
return;
}
// Function to delete the element
// from the back of the deque
template <class X>
void Deque<X>::pop_back()
{
// If deque is empty
if (empty()) {
cout << "Deque underflow" << endl;
abort();
}
// If there is only one character
if (frontIndex == backIndex) {
// Mark deque as empty
// and decrement sizeVar
frontIndex = backIndex = -1;
sizeVar--;
return;
}
// Decrement backIndex cyclically
backIndex = (backIndex - 1 + capacityVar) % capacityVar;
sizeVar--;
return;
}
// Driver Code
int main()
{
// Deque initialization
Deque<int> q;
// Iterate range [1, 100],
// push even numbers at the back
// and push odd numbers at the front
for (int i = 1; i < 10; i++)
if (i % 2 == 0)
q.push_back(i);
else
q.push_front(i);
// Print the current capacity
cout << "Current capacity " << q.capacity() << endl;
// Print the current size
cout << "Current size " << q.size() << endl;
// Print front elements of deque
cout << "Front element " << q.front() << endl;
// Print last element of the deque
cout << "Rear element " << q.back() << endl;
cout << endl;
cout << "Pop an element from front" << endl;
// Pop an element from the front of deque
q.pop_front();
cout << "Pop an element from back" << endl;
// Pop an element from the back of deque
q.pop_back();
cout << endl;
// Print the current capacity
cout << "Current capacity " << q.capacity() << endl;
// Print current size
cout << "Current size " << q.size() << endl;
// Print front elements of deque
cout << "Front element " << q.front() << endl;
// Print last element of the deque
cout << "Rear element " << q.back() << endl;
return 0;
}
Producción
Current capacity 16 Current size 9 Front element 9 Rear element 8 Pop an element from front Pop an element from back Current capacity 16 Current size 7 Front element 7 Rear element 6
Complejidad temporal: O(N)
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por shaadk7865 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA