Estrutura de pilha de dados usando lista vinculada em C++
Este artigo explicará como implementar uma estrutura de dados de pilha usando uma lista vinculada em C++.
Implementar Estrutura de Pilha de Dados Usando Lista Vinculada Simples em C++
Stack é uma estrutura de dados abstrata frequentemente utilizada em programas, sendo os casos de uso mais familiares a memória de pilha do programa.
Este tipo de dado abstrato tem duas operações principais: push e pop. O primeiro realiza a inserção do elemento em cima dos outros elementos e o último remove o elemento mais recente da pilha.
Uma pilha é classificada como estrutura de dados LIFO (último a entrar, primeiro a sair). A pilha pode ser implementada com métodos diferentes, mas vamos construí-la a partir de uma lista vinculada única neste artigo.
Observe que uma pilha só precisa manter o controle do elemento superior, pois é onde as modificações acontecem. Caso contrário, é essencialmente uma coleção sequencial de dados que pode ou não ter uma capacidade fixa. Este último depende da decisão de design que o programador toma.
Os fragmentos de código a seguir implementam uma pilha que pode crescer sem limites de capacidade predefinidos. Em primeiro lugar, definimos um nó de uma lista unida individualmente e typedef como ListNode. Em seguida, declaramos uma classe Stack e incluímos apenas um membro de dados para rastrear o topo da lista.
Neste exemplo, implementaremos apenas as funções push e printNodes. A função de membro push opera de forma semelhante à operação de inserção para a lista vinculada individualmente, exceto que adiciona cada novo elemento no início da lista.
Embora nossa classe Stack tenha o construtor que inicializa o primeiro elemento, essa escolha de design pobre foi tomada apenas para simplificar o código de exemplo deste artigo introdutório.
Por outro lado, a função de membro printNodes não é a função essencial para o tipo de dados da pilha, mas torna a demonstração mais fácil. Isso nos ajuda a verificar se nossa implementação funciona conforme o esperado.
#include <iostream>
#include <string>
#include <vector>
using std::cin;
using std::cout;
using std::endl;
using std::string;
using std::vector;
struct ListNode {
struct ListNode *next = nullptr;
string data;
} typedef ListNode;
class Stack {
public:
explicit Stack(string data) {
top = new ListNode;
top->data = std::move(data);
top->next = nullptr;
};
ListNode *push(string data);
void printNodes();
private:
ListNode *top = nullptr;
};
ListNode *Stack::push(string data) {
auto new_node = new ListNode;
new_node->data = std::move(data);
new_node->next = top;
top = new_node;
return top;
}
void Stack::printNodes() {
auto count = 0;
auto tmp = top;
while (tmp) {
cout << "node " << count << " - data: " << tmp->data << endl;
tmp = tmp->next;
count++;
}
}
int main() {
vector<string> data_set = {"Precise", "Quantal", "Saucy", "Raring"};
Stack s1("Xenial");
for (const auto &item : data_set) {
s1.push(item);
}
s1.printNodes();
return EXIT_SUCCESS;
}
node 0 - data: Raring
node 1 - data: Saucy
node 2 - data: Quantal
node 3 - data: Precise
node 4 - data: Xenial
O código anterior carece da operação pop, que é necessária para que uma estrutura de dados da pilha funcione corretamente. Como implementamos uma pilha ilimitada e nos preocupamos apenas com a simplicidade dos exemplos, as alocações de memória são gerenciadas sob demanda. Cada operação pop invoca delete para liberar a memória mantida pelo elemento anterior no topo. Em um cenário do mundo real, deve-se preferir limitar a capacidade da pilha ou alocar alguma memória com antecedência para melhor desempenho.
Finalmente, precisamos ter um destruidor que libere o objeto depois que ele sai do escopo. A função destruidora itera do elemento top até que nullptr seja encontrado, o que denota o fim da pilha.
#include <iostream>
#include <string>
#include <vector>
using std::cin;
using std::cout;
using std::endl;
using std::string;
using std::vector;
struct ListNode {
struct ListNode *next = nullptr;
string data;
} typedef ListNode;
class Stack {
public:
explicit Stack(string data) {
top = new ListNode;
top->data = std::move(data);
top->next = nullptr;
};
ListNode *push(string data);
void pop();
void printNodes();
~Stack();
private:
ListNode *top = nullptr;
};
ListNode *Stack::push(string data) {
auto new_node = new ListNode;
new_node->data = std::move(data);
new_node->next = top;
top = new_node;
return top;
}
void Stack::pop() {
auto tmp = top->next;
delete top;
top = tmp;
}
Stack::~Stack() {
struct ListNode *tmp = nullptr;
while (top) {
tmp = top->next;
delete top;
top = tmp;
}
}
void Stack::printNodes() {
auto count = 0;
auto tmp = top;
while (tmp) {
cout << "node " << count << " - data: " << tmp->data << endl;
tmp = tmp->next;
count++;
}
}
int main() {
vector<string> data_set = {"Precise", "Quantal", "Saucy", "Raring"};
Stack s1("Xenial");
for (const auto &item : data_set) {
s1.push(item);
}
s1.printNodes();
cout << "/ ------------------------------ / " << endl;
s1.pop();
s1.pop();
s1.printNodes();
return EXIT_SUCCESS;
}
node 0 - data: Raring
node 1 - data: Saucy
node 2 - data: Quantal
node 3 - data: Precise
node 4 - data: Xenial
/ ------------------------------ /
node 0 - data: Quantal
node 1 - data: Precise
node 2 - data: Xenial
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