Stack - Idee und Implementation

Verwendung

Implementation siehe Fortgeschrittene Implementation mit einer Klasse, Optional und generischem Typargument

Stack stack = new Stack<Integer>();
stack.push(10);
stack.push(5);
 
stack.pop(); // Some(5)
stack.pop(); // Some(10)
stack.pop(); // None

Visualisierung

Visualisierung des oberen Codebeispiels

Legende:

• Zuweisung von Variablen oder Attributen: name = Referenz
• Format von Referenzen: Typ@Arbeitsspeicheraddresse
• Wert, welcher null ist (Null-Referenz): Typ@0
• roter Text: Methodenaufrufe
• blaue Pfeile: Aktionen, welcher der Code ausführt

https://excalidraw.com/#json=MNAGF38noFLLYWHn1c4Fa,Dglay-iz__XIufysuBVy5w

Einfache Implementation mit int und zwei Klassen

public class Stack {
    private StackElement head;
 
    public void push(int value) {
        this.head = new StackElement(value, this.head);
    }
 
    public Integer pop() {
        if (this.head == null) {
            return null;
        }
 
        Integer currentHead = this.head.value;
        this.head = this.head.tail;
 
        return currentHead;
    }
 
    private static class StackElement {
        public Integer value;
        public StackElement tail;
 
        public StackElement(int value, StackElement tail) {
            this.value = value;
            this.tail = tail;
        }
    }
}

Einfache Implementation mit int und einer Klasse

package global.oskar.dsa;
 
public class Stack {
    private Integer head;
    private Stack tail;
 
    public Stack() {
        // this is only possible if head is
        // an Integer, not an int
        // since Integer is a class
        this.head = null;
        this.tail = null;
    }
 
    private Stack(int head, Stack tail) {
        this.head = head;
        this.tail = tail;
    }
 
	// returns null if there is no element
	// on top of the stack
    public Integer pop() {
        if (this.head == null) {
            return null;
        }
 
        if (this.tail == null) {
            int currentHead = this.head;
            this.head = null;
 
            return currentHead;
        }
 
        int currentHead = this.head;
        this.head = this.tail.head;
        this.tail = this.tail.tail;
 
        return currentHead;
    }
 
    public void push(int value) {
        if (this.head == null) {
            this.head = value;
            return;
        }
 
        this.tail = new Stack(this.head, this.tail);
        this.head = value;
    }
}

Fortgeschrittene Implementation mit einer Klasse und einem Record, Optional und generischem Typargument

package global.oskar.dsa;
 
import java.util.Optional;
 
public class Stack<T> {
    private StackElement<T> head;
 
    public void push(T value) {
        this.head = new StackElement<>(value, this.head);
    }
 
    public Optional<T> pop() {
        if (this.head == null) {
            return Optional.empty();
        }
 
        T currentHead = this.head.value;
        this.head = this.head.tail;
 
        return Optional.ofNullable(currentHead);
    }
 
    private record StackElement<T>(T value, StackElement<T> tail) {
    }
}

Fortgeschrittene Implementation mit einer Klasse, Optional und generischem Typargument

package global.oskar.dsa;
 
import java.util.Optional;
 
// T is the type of the elements in the Stack
// T is set when creating the stack like:
// Stack ints = new Stack<Integer>();
// or
// Stack strings = new Stack<String>();
public class Stack<T> {
    // head may be null
    private T head;
    private Stack<T> tail;
 
    public Stack() {
        this.head = null;
        this.tail = null;
    }
 
    private Stack(T head, Stack<T> tail) {
        this.head = head;
        this.tail = tail;
    }
 
	// Optional is a type that represents
	// either Some (a value) or None (no value)
	// If there is no element on top
	// then return a None, else a Some
	// containing the value
    public Optional<T> pop() {
        if (this.head == null) {
            return Optional.empty();
        }
 
        if (this.tail == null) {
            final var currentHead = this.head;
            this.head = null;
 
            return Optional.of(currentHead);
        }
 
        final var currentHead = this.head;
        this.head = this.tail.head;
        this.tail = this.tail.tail;
 
        return Optional.of(currentHead);
    }
 
    public void push(T value) {
        if (this.head == null) {
            this.head = value;
            return;
        }
 
        this.tail = new Stack<>(this.head, this.tail);
        this.head = value;
    }
}