Stack-Datenstruktur mit verknüpfter Liste in C++

In diesem Artikel wird erläutert, wie Sie eine Stapeldatenstruktur mithilfe einer verknüpften Liste in C++ implementieren.

Implementieren Sie die Stack-Datenstruktur mithilfe einer einfach verketteten Liste in C++

Stack ist eine abstrakte Datenstruktur, die häufig in Programmen verwendet wird, wobei der bekannteste Anwendungsfall davon der Programm-Stack-Speicher ist.

Dieser abstrakte Datentyp hat zwei Kernoperationen: Push und Pop. Ersteres führt das Einfügen von Elementen über die anderen Elemente durch, und letzteres entfernt das neueste Element aus dem Stapel.

Ein Stack wird als LIFO-Datenstruktur (last in, first out) klassifiziert. Der Stack kann mit verschiedenen Methoden implementiert werden, aber wir werden ihn in diesem Artikel aus einer einfach verketteten Liste aufbauen.

Beachten Sie, dass ein Stack nur das oberste Element verfolgen muss, da dort die Änderungen stattfinden. Andernfalls handelt es sich im Wesentlichen um eine sequentielle Sammlung von Daten, die eine feste Kapazität haben können oder nicht. Letzteres hängt von der Designentscheidung ab, die der Programmierer trifft.

Die folgenden Codeausschnitte implementieren einen Stapel, der ohne vordefinierte Kapazitätsgrenzen wachsen kann. Zuerst definieren wir einen Knoten einer einfach verketteten Liste und typedef ihn als ListNode. Dann deklarieren wir eine Stack-Klasse und fügen nur einen Datenmember hinzu, um den Anfang der Liste zu verfolgen.

In diesem Beispiel implementieren wir nur die Funktionen push und printNodes. Die Memberfunktion push funktioniert ähnlich wie die Einfügeoperation für die einfach verkettete Liste, außer dass sie jedes neue Element am Anfang der Liste hinzufügt.

Obwohl unsere Klasse Stack den Konstruktor hat, der das erste Element initialisiert, wird diese schlechte Designwahl nur getroffen, um den Beispielcode für diesen Einführungsartikel zu vereinfachen.

Andererseits ist die Memberfunktion printNodes nicht die wesentliche Funktion für den Stack-Datentyp, erleichtert aber die Demonstration. Es hilft uns zu überprüfen, ob unsere Implementierung wie beabsichtigt funktioniert.

#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

Im vorherigen Code fehlt die pop-Operation, die für eine ordnungsgemäße Funktion einer Stack-Datenstruktur erforderlich ist. Da wir einen grenzenlosen Stack implementieren und uns nur um die Einfachheit der Beispiele kümmern, werden die Speicherzuweisungen bei Bedarf verwaltet. Jeder pop-Vorgang ruft delete auf, um den Speicher freizugeben, der vom vorherigen Element an oberster Stelle gehalten wird. In einem realen Szenario sollte man es vorziehen, die Kapazität des Stapels zu begrenzen oder im Voraus etwas Speicher zuzuweisen, um eine bessere Leistung zu erzielen.

Schließlich benötigen wir einen Destruktor, der das Objekt freigibt, nachdem es den Gültigkeitsbereich verlassen hat. Die Destruktorfunktion iteriert vom top-Element, bis nullptr gefunden wird, was das Ende des Stapels angibt.

#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