En este artículo, discutiremos cómo crear una cola circular dinámica utilizando una array circular que tiene la siguiente funcionalidad:
- Front(): obtiene el elemento frontal de la cola.
- Atrás(): obtiene el último elemento de la cola.
- Empuje (X): Empuje la X en la cola al final de la cola.
- Pop(): Elimina un elemento de la cola.
A continuación se muestra la ilustración paso a paso:
- Inicialmente, la cola está vacía.
- Inserte el elemento 1 al final de la cola.
- Inserte los elementos 2, 3, 4 al final de la cola.
- Inserte los elementos 5 al final de la cola.
- Pop 4 elementos de la cola.
- Pop 1 elemento de la cola.
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 capacidad , y una array, digamos arr[] para implementar la cola,
- Defina una función, digamos Capacity() para encontrar el tamaño de la array actual utilizada:
- Devolver la capacidad .
- Defina una función, digamos tamaño(), para encontrar el recuento de elementos en la cola:
- Devuelve la variable sizeVar.
- Defina una función diga full() para encontrar si la cola está llena o no:
- Retorna verdadero si sizeVar es igual a capacidad . De lo contrario, devuelve falso.
- Defina una función, diga vacío(), para encontrar si la cola está vacía o no:
- Si frontIndex y backIndex son iguales a -1 , devuelve verdadero. De lo contrario, devuelve falso.
- Defina una función, digamos Front() para imprimir el elemento frontal de la cola :
- Imprime el elemento de arr[frontIndex] si la cola no está vacía() .
- Defina una función, diga Atrás() para imprimir el último elemento de la cola :
- Imprime el elemento de arr[BackIndex] si la cola no está vacía().
- Defina una función, diga Push(X) para insertar un elemento al final de la cola:
- Si la cola está llena , duplique el tamaño de la array actual y copie los elementos de la array anterior en la nueva array.
- Si la cola está vacía() , 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)%capacity y luego asigne X a arr[backIndex] e incremente sizeVar en uno.
- Defina una función, diga Pop(), para eliminar un elemento al principio de la cola:
- Si la cola está vacía, imprima «Subdesbordamiento».
- 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)%capacity 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 defination for queue
template <class X>
class Queue {
private:
// Stores the frontIndex
int frontIndex;
// Stores the back Index
int backIndex;
// Stores the array
X* arr;
// Stores the sizeof queue
int sizeVar;
// Stores the size of array
int capacityVar = 4;
public:
// Queue class constructor
Queue()
{
arr = new X[capacityVar];
frontIndex = backIndex = -1;
sizeVar = 0;
}
// Function Methods
bool empty();
bool full();
void push(X x);
void pop();
X front();
X back();
int capacity();
int size();
};
// Find the capacity of queue
template <class X>
int Queue<X>::capacity()
{
return capacityVar;
}
// Find the number of elements
// present in Queue
template <class X>
int Queue<X>::size()
{
return sizeVar;
}
// Function to check if
// Queue is empty or not
template <class X>
bool Queue<X>::empty()
{
if (frontIndex == -1
&& backIndex == -1)
return true;
else
return false;
}
// Function to check if the queue
// is full or not
template <class X>
bool Queue<X>::full()
{
if (sizeVar == capacityVar)
return true;
else
return false;
}
// Function to find the front element
// of the queue
template <class X>
X Queue<X>::front()
{
// If queue is empty
if (empty()) {
cout << "Queue underflow"
<< endl;
abort();
}
return arr[frontIndex];
}
// Function to find the last element
// of the Queue
template <class X>
X Queue<X>::back()
{
if (empty()) {
cout << "Queue underflow"
<< endl;
abort();
}
return arr[backIndex];
}
// Function to insert the element
// to the rear end of the queue
template <class X>
void Queue<X>::push(X x)
{
if (full()) {
// If the queue 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 in the order of the queue
for (int i = 0, j= frontIndex; i < sizeVar; i++){
temp[i] = arr[j];
j = (j+1) % sizeVar;
}
// update the front and rear indices in the new array
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 the backIndex
backIndex = (backIndex + 1) % capacityVar;
arr[backIndex] = x;
sizeVar++;
return;
}
// Function to pop an element from
// front end of the queue
template <class X>
void Queue<X>::pop()
{
// If queue is empty
if (empty()) {
cout << "Queue underflow"
<< endl;
abort();
}
// If there is only one character
if (frontIndex == backIndex) {
// Mark Queue as empty
// and decrement sizeVar
frontIndex = backIndex = -1;
sizeVar--;
return;
}
// Increment frontIndex cyclically
// using modulo arithmetic
frontIndex = (frontIndex + 1) % capacityVar;
sizeVar--;
return;
}
// Driver Code
int main()
{
// Queue initialization
Queue<int> q;
// Iterate the range [1, 100]
for (int i = 1; i < 5; i++)
q.push(i);
// Print the current capacity
cout << "Current capacity "
<< q.capacity() << endl;
// Print current size
cout << "Current size "
<< q.size() << endl;
// Print front elements of queue
cout << "Front element "
<< q.front() << endl;
// Print last element of the queue
cout << "Rear element "
<< q.back() << endl;
cout << endl;
cout << "Pop an element" << endl;
// Pop an element from the queue
q.pop();
cout << "Pop an element" << endl;
// Pop an element from the queue
q.pop();
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 queue
cout << "Front element "
<< q.front() << endl;
// Print last element of the queue
cout << "Rear element "
<< q.back() << endl;
cout << endl;
cout << "Push element 5" << endl;
cout << "Push element 6" << endl;
q.push(5);
q.push(6);
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 queue
cout << "Front element "
<< q.front() << endl;
// Print last element of the queue
cout << "Rear element "
<< q.back() << endl;
cout << endl;
cout << "Push element 7" << endl;
q.push(7);
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 queue
cout << "Front element "
<< q.front() << endl;
// Print last element of the queue
cout << "Rear element "
<< q.back() << endl;
return 0;
}
Producción:
Current capacity 128 Current size 99 Front element 1 Rear element 99 Pop an element Pop an element Current capacity 128 Current size 97 Front element 3 Rear element 99
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