Datenstrukturen

Queues

Eine Queue (dt. Warteschlangen) ist eine abstrakte Datenstruktur, die einer Liste entspricht. Jedoch können Elemente nur am Anfang eingefügt und am Ende entfernt bzw. gelesen werden.

Die Operationen einer Queue werden enqueue und dequeue genannt. Um ein neues Element in die Warteschlange einzureihen wird die Methode enqueue benutzt, um ein Element aus der Warteschlange zu entfernen oder auszulesen wird die Methode dequeue verwendet.

Der Vorgang läuft nach dem FIFO (First In First Out) Prinzip ab, d.h. Elemente die als erstes in die Queue eingereiht werden, werden auch wieder als erstes daraus entfernt.

FIFO (First In First Out) Strategie
ENQUEUE-Operation ist Spezialform von INSERT
DEQUEUE-Operation ist Spezialform von DELETE
HEADs (Anfang von S), TAILs (Ende von S)

Pseudocode

ENQUEUE(S,k)
begin
    S[TAILs] = k;
    if (TAILs = Länge(S))
    then TAILs := 1;
    else TAILs := TAILs +1;
end

DEQUEUE(S)
begin
    x := S[HEADs];
    if (HEADs = Länge(S))
    then HEADS := 1;
    else HEADs := HEADs + 1;
    RETURN(x);
end

Javacode

public class Queue {
    private Object data;
    private Queue next;
    
    // Konstruktor
    public Queue(Object data) {
        this.data = data;
    }
    
    // get und set Methoden
    public void set_data(Object data) {
        this.data = data;
    }
    public void set_next(Queue next) {
        this.next = next;
    }
    public Object get_data() {
        return this.data;
    }
    public Queue get_next() {
        return this.next;
    }
}

Queue.java

public class QueueList {
    private Queue first;
    private Queue tail;
    private int size;
    
    // Konstruktor
    public QueueList() {
        
    }
    // Methode zum Einfügen eines Elementes
    public void enqueue(Object data) {
        if (tail == null) {
            this.first = this.tail = new Queue(data);
        } else {
            Queue q = new Queue(data);
            tail.set_next(q);
            tail = q; 
        }
        size++;
    }
    
    // Methode zum Löschen eines Elementes
    public Object dequeue() {
        if (first != null) {
            Queue q = first;
            first = q.get_next();
            q.set_next(null);
            size--;
            return q.get_data();
        }
        return null;
    }
    
    public boolean isempty() {
        return first == null;
    }
    public int get_size() {
        return this.size;
    }
}

QueueList.java

public class main {

    /**
     * @param args the command line arguments
     */
    public static void main(String[] args) {
        QueueList myqueue = new QueueList();
        
        // Elemente einfügen
        myqueue.enqueue("1. Element");
        myqueue.enqueue("2. Element");
        myqueue.enqueue("3. Element");
        myqueue.enqueue("4. Element");
        
        // Löschen des ersten Element, da FIFO (First In First Out)
        myqueue.dequeue();
        
        // Ausgabe der Elemente
        while (!myqueue.isempty()) {
            System.out.println(myqueue.dequeue());
        }
    }  
}

main.java

Ausgabe
2. Element
3. Element
4. Element

Stack

Der Stack (auch Stapel oder Keller genannt), ist ein bestimmter Abschnitt im Hauptspeicher, der nach dem LIFO (Last In First Out) Verfahren arbeitet. Daten die zuletzt auf dem Stack gelegt wurden, werden als erstes wieder entfernt.

Durch die Operationen PUSH und POP kann der Stack direkt benutzt werden. PUSH legt Daten auf dem Stack ab, POP nimmt sie wieder herunter.

Der Stack ist ein wichtiger, elementarer Bestandteil, der sehr schnell arbeitet, da es extra reservierte Register dafür gibt. Diese sind zum einen das Stacksegment(SS) und zum anderen der Stackpointer(SP). Bei den Operationen PUSH und POP wird die automatische Stackverwaltung durch die Register SS und SP benutzt.

LIFO (Last In First Out) Strategie
PUSH-Operation ist Spezialform von INSERT
POP-Operation ist Spezialform von DELETE
Index Tops, gibt stets die Position des zuletzt eingefügten Elements an

Pseudocode

PUSH(S,k)
begin
    if (STACK_VOLL)
    then ERROR;
    else begin
         Tops = Tops + 1;
         S[Tops] := k;
    end
end

STACK_VOLL(S)
begin
	if(Tops = Länge(S))
    then RETURN TRUE;
    else RETURN FALSE;
 	end
end

POP(S)
begin
    if (STACK_LEER)
    then ERROR
    else begin
         Tops = Tops - 1;
         RETURN (S[Tops+1];
    end
end

STACK_LEER(S)
begin
	if(Tops = 0)
    then RETURN TRUE;
    else RETURN FALSE;
 	end
end

Javacode

public class Stack {
    private int top;
    private int size;
    private int[] stackArray;

    public Stack(int arraySize) {
        size=arraySize;
        stackArray = new int[size];
        top=-1;
    }
    public void PUSH(int value) {
        if (top == size-1) {
            System.out.println("Stack ist voll");
        } else {
            top = top + 1;
            stackArray[top] = value;
        }
    }
    public int POP() {
        if (!isempty()) {
            top = top - 1;
            return stackArray[top + 1];
        } else {
           System.out.println("Stack ist leer");
        }
        return 0;
    }
    public boolean isempty() {
        return top == -1;
    }
    public void print() {
        for (int i=0; i<top+1 ; i++) {
            System.out.println(stackArray[i]);
        }
    }
}

Stack.java

public class main {

    /**
     * @param args the command line arguments
     */
    public static void main(String[] args) {
        Stack s = new Stack(5);
        s.PUSH(1);
        s.PUSH(2);
        s.PUSH(3);
        s.PUSH(4);
        s.PUSH(5);
        s.print();
        System.out.println("");
        
        s.POP();
        s.POP();
        s.print();
    }
}

main.java

Ausgabe
Ausgabe des Stacks nach PUSH
1
2
3
4
5
Ausgabe des Stacks nach POP
1
2
3

Mit Programmier-Skills perfekt für die Zukunft aufgestellt! Die Kurse gehen schon bei 11,99 € los!

Listen

Einfach verkettete Listen

Verkettete Listen bestehen aus beliebig vielen Listenelementen, die Objekte speichern. Ein Listenelement besitzt neben einem Objekt, auch einen Zeiger auf das nächste Element. Somit kennt Element 1, Element 2, Element 2 kennt Element 3 usw.

Möchte man nun auf die Liste zugreifen, indem man zum Beispiel nach einem Element sucht, beginnt man bei Listenelement 1 und kontrolliert ob es sich hierbei um das zu suchende Element handelt. Ist dies nicht der Fall, verweist Element 1 auf seinen Nachfolger. Somit wird die komplette Liste durchlaufen, bis ein Element keinen Nachfolger mehr hat, oder das Element gefunden wurde.

Java verfügt über einen vordefinierte Klasse - die Klasse LinkedList, mit deren Hilfe verkettete Listen implementiert werden können. Sie stellt Methoden zur Verfügung, um Objekte der Liste hinzuzufügen, zu entfernen oder zu bearbeiten. Des Weiteren gibt es eine Schnittstelle ListIterator, um auf Positionen innerhalb einer Liste zuzugreifen.
Hier findest du alle Methoden der Klasse LinkedList
https://docs.oracle.com/javase/7/docs/api/java/util/LinkedList.html

einfach verkettete liste - java, pseudocode

Doppelt verkettete Listen

Die doppelt verkettete Liste hat neben dem next-Zeiger zusätzlich einen preview-Zeiger. Also einen Zeiger auf das Vorgängerelement.

Lineare Anordnung der Daten
keine Indizes
Reihenfolge wird durch Zeiger innerhalb des Objektes bestimmt

Pseudocode - Doppelt verkettete Liste

LIST_INSERT(l,x)
begin
    x↑.next := HEAD;
    if (HEAD ≠ nil)
    then HEAD↑.prev := x;
    HEAD = x;
    x↑.prev = nil;
end

LIST_DELETE(l,x)
begin
    if(x↑.prev ≠ nil)
    then x↑.prev↑.next = x↑.next;
    else begin
    	 HEAD = x↑.next;
    end
    if (x↑.next ≠ nil)
    then x↑.next↑.prev = x↑.prev;
end

LIST_SEARCH(l,x)
begin
    x := HEAD;
    while (x ≠ nil and x↑.key ≠ k)
    do x := x↑.next;
    RETURN(x);
end

Javacode

package verkettete.liste;
import java.util.LinkedList;
import java.util.ListIterator;

public class VerketteteListe {

    /**
     * @param args the command line arguments
     */
    public static void main(String[] args) {
        LinkedList list = new LinkedList();
        list.addFirst("Thomas");
        list.addFirst("Max");
        list.addFirst("Hannah");
        
        ListIterator iter = list.listIterator();
        iter.next();
        iter.add("Lisa");
        iter.next();
        iter.next();
        iter.add("Lukas");
        
        iter = list.listIterator();
        while(iter.hasNext()) {
            System.out.println(iter.next());
        }
    } 
}

Queue.java

Ausgabe
Hannah
Lisa
Max
Thomas
Lukas

keyboard_arrow_left