Estructura de datos de pila usando una lista enlazada en C++

Este artículo explicará cómo implementar una estructura de datos de pila usando una lista vinculada en C++.

Implementar la estructura de datos de la pila usando una lista enlazada individual en C++

La pila es una estructura de datos abstracta que se utiliza con frecuencia en los programas, siendo los casos de uso más familiares la memoria de la pila del programa.

Este tipo de datos abstracto tiene dos operaciones principales: push y pop. El primero realiza la inserción del elemento encima de los otros elementos y el segundo elimina el elemento más reciente de la pila.

Una pila se clasifica como estructura de datos LIFO (último en entrar, primero en salir). La pila se puede implementar con diferentes métodos, pero la construiremos a partir de una lista enlazada individualmente en este artículo.

Tenga en cuenta que una pila solo necesita realizar un seguimiento del elemento superior, ya que es donde ocurren las modificaciones. De lo contrario, es esencialmente una recopilación secuencial de datos que pueden tener o no una capacidad fija. Esto último depende de la decisión de diseño que tome el programador.

Los siguientes fragmentos de código implementan una pila que puede crecer sin límites de capacidad predefinidos. Al principio, definimos un nodo de una lista enlazada individualmente y lo typedef como ListNode. Luego declaramos una clase Stack e incluimos solo un miembro de datos para rastrear la parte superior de la lista.

En este ejemplo, solo implementaremos las funciones push y printNodes. La función de miembro push opera de manera similar a la operación de inserción para la lista enlazada individualmente, excepto que agrega cada elemento nuevo al principio de la lista.

Aunque nuestra clase Stack tiene el constructor que inicializa el primer elemento, esta mala elección de diseño solo se toma para simplificar el código de ejemplo para este artículo introductorio.

Por otro lado, la función miembro printNodes no es la función esencial para el tipo de datos de pila, pero facilita la demostración. Nos ayuda a verificar que nuestra implementación funciona según lo previsto.

#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

El código anterior carece de la operación pop, que es necesaria para que una estructura de datos de pila funcione correctamente. Dado que implementamos una pila ilimitada y solo nos preocupamos por la simplicidad de los ejemplos, las asignaciones de memoria se administran bajo demanda. Cada operación pop invoca remove para liberar la memoria que tenía el elemento anterior en la parte superior. En un escenario del mundo real, uno debería preferir limitar la capacidad de la pila o asignar algo de memoria por adelantado para un mejor rendimiento.

Finalmente, necesitamos tener un destructor que libere el objeto después de que salga del alcance. La función destructora itera desde el elemento top hasta que se encuentra nullptr, que denota el final de la pila.

#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