IT-Academy Logo
Sign Up Login Help
Home - Programmieren - Java - Grundlegende Datenstrukturen: Stacks, Queues & Lists



Grundlegende Datenstrukturen: Stacks, Queues & Lists

Implementierung in Java.


Autor: Alexander Zirl (Sliver)
Datum: 20-10-2003, 19:14:22
Referenzen: keine
Schwierigkeit: Anfänger
Ansichten: 28099x
Rating: 9 (2x bewertet)

Hinweis:

Für den hier dargestellte Inhalt ist nicht der Betreiber der Plattform, sondern der jeweilige Autor verantwortlich.
Falls Sie Missbrauch vermuten, bitten wir Sie, uns unter missbrauch@it-academy.cc zu kontaktieren.

[Druckansicht] [Als E-Mail senden] [Kommentar verfassen]



Einleitung

Es gibt viele Gründe, die dafür sprechen sogenannte dynamische Datenstrukturen wie Stacks (dt. Stapel), Queues (dt. [Warte]Schlangen) oder Lists (Listen) zu verwenden. Der Array (dt. Reihe bzw. Feld) bietet schon eine komfortable Lösung, um eine Reihe von Werten und Attribute zu speichern. Jedoch gibt es einen ganz besonderen Nachteil beim Array: er ist statisch. Auf gut Deutsch heißt das, dass man die Größe eines Array nicht verändern kann, weder vergrößern, noch verkleinern.

Auf den ersten Blick scheint dies für den Newcomer kein Problem darzustellen, denn man könnte ja einfach einen Array mit einer überdimensionalen Größe angeben, so dass der Speicher immer reicht. Nun, dies ist auch im Zeitalter von 512, 1024 oder gar mehr MB als Hauptspeicher nicht wirklich zu empfehlen, da große Mengen an Speicher verschwendet werden und die Initialisierung viel länger als nötig dauert. Außderdem dauern Array-Operationen relativ lange, was die Performance negativ beeinflusst. Man nehme nur mal an, man hat einen Array von 10000 Einträgen, und man möchte ca. die Hälfte von diesen löschen. Wenn diese 5000 Einträge relativ weit in der Mitte liegen, so dass weit am Ende des Arrays sich weiterhin Einträge befinden, wird ein Such-Algorithmus viel Zeit mit den mittleren leeren Einträgen verbringen, die gar nicht nötig sind. Natürlich könnte man die Daten re-positionieren, so dass nur am Ende eine Lücke klafft, was sich bei einem Array allerdings als sehr umständlich und zeitaufwendig herausstellt.

Lists (Listen)

Um den einfachen Problemen eines Arrays abhilfe zu schaffen, wurden Listen erfunden. Listen haben den Vorteil, dass sie eine dynamische Datenstruktur sind, d.h. ihre größe kann sich anpassen. Diese Datenstruktur besteht immer aus zwei Klassen, einmal die Klasse für die Knotenpunkte, die Knotenattribute wie Wert, NächsterKnoten, etc. speichert. Die zweite Klasse ist die Liste selbst. Die folgende Implementation hat 2 Klassen:
  • Liste.java :: repräsentiert die Liste
  • Knoten.java :: repräsentiert die Knotenpunkte
Bei jeder Funktion ist es wichtig, dass die Pointer zu den einzelnen Knoten nicht verloren gehen, und während einer Prozedur zwischengespeichert werden, so dass man die Liste wie gewünscht manipulieren kann. Das ist der wichtigste Punkt!
Zusätzlich zu den Hauptfunktionen entfernen(Knoten), einfuegenVorne(Knoten), getWurzel() und setzeWurzel() habe ich noch weitere hinzugefügt. Diese illustrieren und helfen bei weiteren Funktionsimplementationen, wie solchen, die z.B. bei einer doppelt-gelinkten (vorwärts und rückwärts Links) nötig sind.



(Source Code am Ende des Artikels)

Stacks (Stapel)

Stacks sind ein relativ einfaches Konstrukt wenn man mit Listen vertraut ist. Ein Stack ist, wie der Name schon verrät, eine Art Stapel, d.h. man kann Elemente nur von oben wegnehmen (pop) bzw. drauflegen (push). Jegliche Zusatzfunktionen entfallen und sind nicht im Sinne eines eigentlichen Stacks.

Im Klartext heißt das: Ein Stack ist eine Liste, zu der man Elemente nur vorne einfügen kann und nur von vorne wegnehmen kann. Die einzigen Methoden sind:
  • push (drauflegen)
  • pop (wegnehmen)
  • get (das oberste Element anschauen)


Diese Konstruktion macht natürlich nur in Situationen Sinn, in denen man ein solches Geschehen simulieren will - ansonsten könnte man auch gleich zu einer Liste wechseln. Ein Stack simuliert ein LIFO-Verhalten: Last In First Out (das Element, welches zuletzt hinzugefügt wurde, wird auch als erstes wieder runtergenommen). LIFO ist ein wichtiges Konzept auf verschiedenen Ebenen der Programmierung.

Ein Beispiel ist die Simulation der Ablegung von return-Variablen im Speicher. Wenn eine Funktion aufgerufen wird, wird für diese Speicher direkt auf dem Stack freigemacht (push). Wenn die Funktion endet, popped das Programm den ersten Eintrag vom Stack (die return variable) wieder runter.

Details zur Implementation können von der Liste übernommen werden.

Queues ([Warte]Schlangen)

Queues zeigen ein ähnliches Verhalten wie Stacks, außer, dass sie ein FIFO-Verhalten simulieren. FIFO bedeuted First In First Out, d.h. das Element was zuerst eingefügt wird, kommt auch zuerst wieder raus: Wie in einer Warteschlange im richtigen Leben. Die Implementation ähnelt der des Stacks und der Liste.



Zusammenfassung

Die drei beschriebenen Datenstrukturen sind einfach, aber essenziell und sind Teil der fundamentalen Datenstrukturen der Objekt-Orientierten Programmierung. Die Funktionen einer List können - mehr oder weniger - beliebig ausgeweitet werden, wie z.B. Such- und Sortierfunktionen. Die gezeigten Funktionen stellen nur die grundlegenden Methoden dar.

Appendix: Source Code
Liste.java
-----------------------------------------------------------
/**
*
* Author: Alexander Zirl
* Datum: 02.10.2003
* Beschreibung: Liste.java - Implementierung einer Liste
*
**/

public class Liste
{
private Knoten wurzel = null;
private Knoten ende = null;

public Liste( Knoten wurzel)
{
   this.setzeWurzel( wurzel);
   this.setzeEnde( wurzel);
}
public Liste()
{}

public Knoten getWurzel()
{ return this.wurzel; }
public Knoten getEnde()
{ return this.ende; }

public void setzeWurzel( Knoten knoten)
{ this.wurzel = knoten; }
public void setzeEnde( Knoten knoten)
{ this.ende = knoten; }

public void einfuegenAufsteigend( Knoten knoten)
{
  if( !ersterEintrag( knoten))
  {
  if( knoten.getWert() <= this.getWurzel().getWert())
    einfuegenVorne( knoten);
  else if( knoten.getWert() >= this.getEnde().getWert())
    einfuegenHinten( knoten);
  else
  {
    Knoten momentanerKnoten = this.getWurzel();
    Knoten letzterKnoten = null;

    while( momentanerKnoten != null)
    {
      if(momentanerKnoten.getWert() >= knoten.getWert())
      {
        letzterKnoten.setzeVorne( knoten);
          knoten.setzeVorne( momentanerKnoten);
          break;
        }
        letzterKnoten = momentanerKnoten;
        if((momentanerKnoten = momentanerKnoten.getVorne()) == null) break;
      }
    }
  }
}
public void einfuegenHinten( Knoten knoten)
{
  if( !ersterEintrag( knoten))
  {
    this.ende.setzeVorne( knoten);
    this.ende = knoten;
  }
}
public void einfuegenVorne( Knoten knoten)
{
  if( !ersterEintrag( knoten))
  {
    knoten.setzeVorne( this.getWurzel());
    this.setzeWurzel( knoten);
  }
}

public Knoten finden( int wert)
{
  Knoten momentanerKnoten = this.getWurzel();

  while( momentanerKnoten != null)
  {
    if( momentanerKnoten.getWert() == wert)
      return momentanerKnoten;

    momentanerKnoten = momentanerKnoten.getVorne();
  }
  return null;
}

public Knoten entfernen( int wert)
{
  Knoten momentanerKnoten = this.getWurzel();
  Knoten letzterKnoten = null;

  while( momentanerKnoten != null)
  {
    if( momentanerKnoten.getWert() == wert)
    {
      letzterKnoten.setzeVorne( momentanerKnoten.getVorne());
      return momentanerKnoten;
    }
    letzterKnoten = momentanerKnoten;
    momentanerKnoten = momentanerKnoten.getVorne();
  }
  return null;
}

public boolean ersterEintrag( Knoten knoten)
{
  if( this.getWurzel() != null)
    return false;
  else
  {
    this.setzeWurzel( knoten);
    this.setzeEnde( knoten);
    return true;
  }
}
}

Knoten.java
-----------------------------------------------------------
/**
*
* Author: Alexander Zirl
* Datum: 02.10.2003
* Beschreibung: Knoten.java
* Implementierung eines Knotens für eine Liste (s. Liste.java)
*
**/

public class Knoten
{
  private int wert;
  private Knoten vorne = null;
  //private Knoten hinten;

public Knoten( int originalWert)
{ this.wert = originalWert; }

public Knoten getVorne()
{ return this.vorne; }

public int getWert()
{ return this.wert; }

public void setzeWert( int neuerWert)
{ this.wert = neuerWert; }

public void setzeVorne( Knoten neuerVorne)
{ this.vorne = neuerVorne; }
}

TestDatenstrukturen.java
-----------------------------------------------------------
/**
*
* Author: Alexander Zirl
* Datum: 02.10.2003
* Beschreibung: TestDatenstrukturen.java
* Test-Main-Funktion für Listen, Stacks und Queues
*
**/

public class TestDatenstrukturen
{
public static void main( String[] args)
{
  Liste liste = new Liste();
  Knoten eins = new Knoten( 1);
  Liste liste2 = new Liste( eins);

  liste.einfuegenHinten( new Knoten( 3));
  liste.einfuegenVorne( new Knoten(5)); // liste = {5,3}
  liste2.einfuegenHinten( new Knoten(4));
  liste2.einfuegenAufsteigend( new Knoten(5)); // liste2 = { 1, 4, 5}
  liste2.entfernen( liste.getWurzel().getWert());

  Knoten listeKnoten = liste.getWurzel();
  Knoten liste2Knoten = liste2.getWurzel();

  System.out.println( "No.\t\tListe1:\t\tListe2:");
  for( int i=0; listeKnoten != null || liste2Knoten != null; i++)
  {
    System.out.print( i + ".\t\t");
    if (listeKnoten != null) {
      System.out.print( listeKnoten.getWert());
      listeKnoten = listeKnoten.getVorne();
    }
    if (liste2Knoten != null) {
      System.out.print( "\t\t" + liste2Knoten.getWert());
      liste2Knoten = liste2Knoten.getVorne();
    }
    System.out.print( "\n");
  }
}
} 


[back to top]



Userdaten
User nicht eingeloggt

Gesamtranking
Werbung
Datenbankstand
Autoren:04508
Artikel:00815
Glossar:04116
News:13565
Userbeiträge:16552
Queueeinträge:06246
News Umfrage
Ihre Anforderungen an ein Online-Zeiterfassungs-Produkt?
Mobile Nutzung möglich (Ipone, Android)
Externe API Schnittstelle/Plugins dritter
Zeiterfassung meiner Mitarbeiter
Exportieren in CSV/XLS
Siehe Kommentar



[Results] | [Archiv] Votes: 1154
Comments: 0