Implementar una estructura de datos de cola usando una lista vinculada en C++
Este artículo explicará cómo implementar una estructura de datos de cola usando una lista enlazada en C++.
Implementar la estructura de datos de la cola usando una lista enlazada individualmente en C++
Una cola es una estructura de datos que administra sus elementos en forma FIFO (primero en entrar, primero en salir), por lo que el primer elemento agregado será el primero en ser eliminado de la cola.
Generalmente, las operaciones de inserción y eliminación para la estructura de datos de la cola se denominan poner y quitar de la cola, respectivamente. Se puede implementar una cola abstracta utilizando diferentes métodos y estructuras de datos. Por lo general, el lado en el que se agregan nuevos elementos se llama - front, mientras que el lado desde el que se eliminan los elementos - una parte posterior de la cola.
En los siguientes ejemplos, implementamos la cola utilizando la lista enlazada individualmente, que consta de nodos que almacenan el objeto de datos y el puntero al siguiente nodo. En este caso, elegimos representar un objeto de datos con un solo objeto de cadena por simplicidad, pero depende del programador diseñar la estructura de nodo más óptima.
A continuación, podemos definir una clase llamada Queue, que incluye tres miembros de datos: front, back y size. Los dos primeros se explican por sí mismos, mientras que el último denota el recuento actual de elementos de la cola. Puede haber dos variantes principales de la estructura de datos de la cola ilimitadas y delimitadas, la primera de las cuales puede agregar elementos hasta que haya memoria disponible. Por otro lado, una cola limitada está diseñada para almacenar solo un número fijo de elementos.
En este artículo, diseñamos una cola ilimitada, pero el lector puede desarrollar intuitivamente la delimitada con pequeñas modificaciones en los ejemplos de código dados. Dado que estamos implementando una cola ilimitada desde cero, necesitamos administrar las asignaciones de memoria dinámica a medida que la cola crece. Por lo tanto, las funciones miembro enQueue y deQueue incluirán operadores new y remove. Tenga en cuenta que esta implementación de la cola no pretende ser eficiente, sino que demuestra los mecanismos de trabajo básicos de esta estructura de datos en general.
Nuestra Queue tiene dos constructores, uno de los cuales toma initializer_list de valores de cadena e invoca la función enQueue varias veces para construir un objeto Queue. Cada invocación de enQueue incrementa el miembro size, y si es necesario, el usuario de la clase puede recuperar su valor utilizando la función getSize. También implementamos una función auxiliar printNodes para inspeccionar el contenido del objeto Queue dado. Esta función no necesita estar definida en un escenario del mundo real, pero puede ser útil para probar y depurar.
#include <iostream>
#include <string>
using std::cin;
using std::cout;
using std::endl;
using std::string;
struct ListNode {
struct ListNode *next = nullptr;
string data;
} typedef ListNode;
class Queue {
public:
explicit Queue() {
back = front = nullptr;
size = 0;
};
Queue(std::initializer_list<string> list);
ListNode *enQueue(string data);
string deQueue();
void printNodes();
size_t getSize() const;
~Queue();
private:
ListNode *front;
ListNode *back;
size_t size;
};
Queue::Queue(std::initializer_list<string> list) {
front = back = nullptr;
size = 0;
for (const auto &item : list) {
enQueue(item);
}
}
ListNode *Queue::enQueue(string data) {
auto new_node = new ListNode;
new_node->data = std::move(data);
new_node->next = nullptr;
if (front == nullptr) {
front = back = new_node;
size++;
return new_node;
}
back->next = new_node;
back = back->next;
size++;
return new_node;
}
void Queue::printNodes() {
auto count = 0;
auto tmp = front;
while (tmp) {
cout << "node " << count << " - data: " << tmp->data << endl;
tmp = tmp->next;
count++;
}
}
size_t Queue::getSize() const { return size; }
int main() {
Queue q1 = {"Precise", "Quantal", "Saucy", "Raring"};
q1.printNodes();
cout << "queue size = " << q1.getSize() << endl;
cout << "/ ------------------------------ / " << endl;
q1.enQueue("Xenial");
q1.enQueue("Bionic");
q1.printNodes();
cout << "queue size = " << q1.getSize() << endl;
return EXIT_SUCCESS;
}
Producción :
node 0 - data: Precise
node 1 - data: Quantal
node 2 - data: Saucy
node 3 - data: Raring
queue size = 4
/ ------------------------------ /
node 0 - data: Precise
node 1 - data: Quantal
node 2 - data: Saucy
node 3 - data: Raring
node 4 - data: Xenial
node 5 - data: Bionic
queue size = 6
La clase anterior Queue carece de la implementación del destructor y de la función para eliminar elementos de la cola. Estos dos se definen en el siguiente fragmento de código, y el código del controlador correspondiente se incluye en la función main del programa.
La función deQueue está diseñada para devolver un valor de cadena específico de nuestra implementación. En consecuencia, esta función devuelve una cadena vacía para indicar que la cola está vacía y el usuario es responsable de verificar el valor devuelto. Mientras tanto, la función destructora se asegura de que toda la memoria asignada se libere antes de que el objeto salga del alcance.
#include <iostream>
#include <string>
using std::cin;
using std::cout;
using std::endl;
using std::string;
struct ListNode {
struct ListNode *next = nullptr;
string data;
} typedef ListNode;
class Queue {
public:
explicit Queue() {
back = front = nullptr;
size = 0;
};
Queue(std::initializer_list<string> list);
ListNode *enQueue(string data);
string deQueue();
void printNodes();
size_t getSize() const;
~Queue();
private:
ListNode *front;
ListNode *back;
size_t size;
};
Queue::Queue(std::initializer_list<string> list) {
front = back = nullptr;
size = 0;
for (const auto &item : list) {
enQueue(item);
}
}
ListNode *Queue::enQueue(string data) {
auto new_node = new ListNode;
new_node->data = std::move(data);
new_node->next = nullptr;
if (front == nullptr) {
front = back = new_node;
size++;
return new_node;
}
back->next = new_node;
back = back->next;
size++;
return new_node;
}
string Queue::deQueue() {
if (front == nullptr)
return "";
else {
auto tmp = front->next;
auto data = front->data;
delete front;
front = tmp;
size--;
return data;
}
}
Queue::~Queue() {
struct ListNode *tmp = nullptr;
while (front) {
tmp = front->next;
delete front;
front = tmp;
}
}
void Queue::printNodes() {
auto count = 0;
auto tmp = front;
while (tmp) {
cout << "node " << count << " - data: " << tmp->data << endl;
tmp = tmp->next;
count++;
}
}
size_t Queue::getSize() const { return size; }
int main() {
Queue q1 = {"Precise", "Quantal", "Saucy", "Raring"};
auto ret = q1.deQueue();
if (!ret.empty())
cout << ret << endl;
else
cout << "Queue is empty!" << endl;
cout << "queue size = " << q1.getSize() << endl;
cout << "/ ------------------------------ / " << endl;
while (!q1.deQueue().empty())
;
cout << "queue size = " << q1.getSize() << endl;
ret = q1.deQueue();
if (!ret.empty())
cout << ret << endl;
else
cout << "Queue is empty!" << endl;
for (int i = 0; i < 100; ++i) {
q1.enQueue("hello");
}
q1.printNodes();
cout << "queue size = " << q1.getSize() << endl;
return EXIT_SUCCESS;
}
Precise
queue size = 3
/ ------------------------------ /
queue size = 0
Queue is empty!
queue size = 100
Founder of DelftStack.com. Jinku has worked in the robotics and automotive industries for over 8 years. He sharpened his coding skills when he needed to do the automatic testing, data collection from remote servers and report creation from the endurance test. He is from an electrical/electronics engineering background but has expanded his interest to embedded electronics, embedded programming and front-/back-end programming.
LinkedIn Facebook