Implementierung eines Stacks mit dyn. Speicherallokation

Michael Hahsler

Implementieren Sie die Datenstruktur Stack. Ein Stack oder Stapelspeicher verwendet zur Speicherung das LIFO-Prinzip (last in - first out). Man kann sich den Stack als einen Turm aus Bauklötzen die eine Nummer haben (Repräsentieren die Daten), vorstellen. Durch die Operation push(Daten) kann ein neuer Bauklotz auf den Turm gelegt werden. Die Operation Daten=pop nimmt den obersten Bauklotz vom Turm und liefert die Nummer auf dem Klotz (die Daten) zurück.

UML Klassendiagramm:

$\begin{figure} \begin{center} \leavevmode \epsfxsize =14cm \epsffile {stack_uml.eps}\end{center}\end{figure}$

Repräsentation des Stacks als Liste:

$\begin{figure} \begin{center} \leavevmode \epsfxsize =14cm \epsffile {stack_strukt.eps}\end{center}\end{figure}$

Hinweise:

Verwenden sie eine vereinfachte Listenstruktur (einfach gelinkte Liste, eingefügen und löscht nur am Anfang).
Bei push(Data) wird dynamisch ein neus Element erzeugt und in die Liste eingebaut.
Bei Data=pop wird das Element aus der Liste entfernt und zerstört.
Die Daten in Element sind vom Typ int.

Hinweise:


#include <iostream.h>
#include "stack.h"

main()
{
  Stack  a_stack;
  for (int i=0; i<10; i++)
  {
    cout << "push: " << i << endl;
    a_stack.push(i);
  }
  while (!a_stack.is_empty()) {
    cout << "pop: " << a_stack.pop() << " -> ";
    cout << "empty=" << a_stack.is_empty() << endl;
  }
}

Lösung: Code

Index: Contents