Implementar uma estrutura de dados de fila usando lista vinculada em C++
Este artigo explicará como implementar uma estrutura de dados de fila usando uma lista vinculada em C++.
Implementar a estrutura de dados da fila usando uma lista vinculada em C++
Uma fila é uma estrutura de dados que gerencia seus elementos de maneira FIFO (first-in-first-out), de forma que o primeiro elemento adicionado será o primeiro a ser removido da fila.
Geralmente, as operações de inserção e remoção para a estrutura de dados da fila são referidas como enfileirar e retirar da fila, respectivamente. Uma fila abstrata pode ser implementada usando diferentes métodos e estruturas de dados. Normalmente, o lado no qual os novos elementos são adicionados é chamado - frente, enquanto o lado do qual os elementos são removidos - uma parte traseira da fila.
Nos exemplos a seguir, implementamos a fila usando a lista vinculada individualmente, que consiste em nós que armazenam o objeto de dados e o ponteiro para o próximo nó. Neste caso, optamos por representar um objeto de dados com um único objeto string para simplificar, mas cabe ao programador projetar a estrutura de nó mais ideal.
A seguir, podemos definir uma classe chamada Queue, que inclui três membros de dados: front, back e size. Os dois primeiros são autoexplicativos, enquanto o último denota a contagem atual de elementos da fila. Pode haver duas variantes principais da estrutura de dados da fila ilimitada e limitada; a primeira pode adicionar elementos até que haja memória disponível. Por outro lado, uma fila limitada é projetada para armazenar apenas um número fixo de elementos.
Neste artigo, projetamos uma fila ilimitada, mas o leitor pode desenvolver intuitivamente a fila limitada com pequenas modificações nos exemplos de código fornecidos. Como estamos implementando uma fila ilimitada do zero, precisamos gerenciar as alocações de memória dinâmica à medida que a fila cresce. Assim, as funções-membro enQueue e deQueue incluirão os operadores new e remove. Observe que esta implementação da fila não tem a intenção de ser eficiente, mas sim demonstrar os mecanismos básicos de funcionamento dessa estrutura de dados em geral.
Nossa Queue tem dois construtores, um dos quais pega initializer_list de valores de string e invoca a função enQueue várias vezes para construir um objeto Queue. Cada invocação enQueue incrementa o membro size e, se necessário, o usuário da classe pode recuperar seu valor usando a função getSize. Também implementamos uma função auxiliar printNodes para inspecionar o conteúdo de um determinado objeto Queue. Esta função não precisa ser definida em um cenário do mundo real, mas pode ser útil para teste e depuração.
#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;
}
Produção:
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
A classe Queue anterior carece da implementação do destruidor e da função para remover elementos da fila. Esses dois são definidos no seguinte trecho de código, e o código do driver correspondente está incluído na função main do programa.
A função deQueue é projetada para retornar um valor de string específico para nossa implementação. Conseqüentemente, essa função retorna uma string vazia para denotar que a fila está vazia e que o usuário é responsável por verificar o valor de retorno. Enquanto isso, a função destruidora garante que toda a memória alocada seja liberada antes que o objeto saia do escopo.
#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