Steque & Deque

Kirby.exe

Kirby.exe

Top Contributor
Also wir sollen zwei Datenstrukturen implementieren:

Einmal einen Steque welcher intern mit zwei Stack funktioniert. Hier darf man sowohl von links als auch rechts (also eher von oben oder von unten) auf den Stack stuff legen. Jedoch darf man hier nur von links (eher gesagt von oben) poppen. Dies habe ich so gemacht:

Java:
import java.util.Stack;

public class Steque<T> {
    
    private Stack<T> leftStack;
    private Stack<T> rightStack;
    private int size;
    
    public Steque() {
        this.leftStack = new Stack<>();
        this.rightStack = new Stack<>();
        size = 0;
    }
    
    public int size() {
        return size;
    }
    
    public boolean isEmpty() {
        return this.size() == 0;
    }
    
    public void pushLeft(T elem) {
        this.leftStack.push(elem);
        size++;
    }
    
    public void pushRight(T elem) {
        this.rightStack.push(elem);
        size++;
    }
    
    public T popLeft() {
        if(this.leftStack.size() == 0) {
            this.swapStacks();
        }
        if(this.leftStack.size() != 0)  size--;
        return this.leftStack.size() != 0 ? this.leftStack.pop() : null;
    }
    
    private void swapStacks() {
        while(this.rightStack.size() != 0) {
            this.leftStack.push(this.rightStack.pop());
        }
    }
}

Bei Deque hänge ich etwas fest, da man hier noch on Top von den Funktionen von Steque eine popRight() funktion bekommt. Sprich man darf auch von rechts oder eher gesagt von unten poppen.

Hier könnte das bei falscher oder schlechter Implementation zu einer Laufzeit Katastrophe führen, wenn man es z.B. wie beim Steque macht xD Da wenn der linke Stack leer ist und der rechte nicht und man nun von links poppen möchte, dann werden alle Elemente in den linken Stack gepusht. Wenn ich danach aber wieder von rechts poppen möchte, muss alles wieder rübergeschoben werde. Sollte dies immer im wechsel passieren ist das bei der gedachten implementieren eine Katastrophe.

Wir dürfen bei Deque anstatt zwei sogar drei Stacks nutzen, ich verstehe aber nicht ganz wie ich diesen verwenden soll.

Meine Idee:

Ich könnte, wenn einer der links oder rechts Stacks leer ist, den "vollen" Stack halbieren und die zwei teile auf die Stacks aufteilen. Dies würde die Laufzeit schonmal boosten. Hier wüsste ich aber not really wie ich das Ding in gescheiter Laufzeit partitioniere... :(

Ich habe hier mal meinen Versuch:

Java:
import java.util.Stack;

public class Deque<T> {
    
    private Stack<T> leftStack;
    private Stack<T> rightStack;
    private Stack<T> movingStack;
    private int movingMode;
    private int size;
    
    public Deque() {
        this.leftStack = new Stack<>();
        this.rightStack = new Stack<>();
        this.movingStack = new Stack<>();
        size = 0;
        this.movingMode = -1;
    }
    
    public int size() {
        return size;
    }
    
    public boolean isEmpty() {
        return this.size() == 0;
    }
    
    public void pushLeft(T elem) {
        this.leftStack.push(elem);
        size++;
    }
    
    public void pushRight(T elem) {
        this.rightStack.push(elem);
        size++;
    }
    
    public T popLeft() {
        if(this.leftStack.size() == 0) {
            this.partionStacks();
        }
        
        if(this.leftStack.size() != 0) {
            size--;
            return this.leftStack.pop();
        }
        
        return null;
    }
    
    public T popRight() {
        if(this.rightStack.size() == 0) {
            this.partionStacks();
        }
        
        if(this.rightStack.size() != 0) {
            size--;
            return this.rightStack.pop();
        }
        
        return null;
    }
    
    private void createMovingStack() {
        if(this.rightStack.size() == 0) {
            while(this.leftStack.size() != 0) {
                this.movingStack.push(this.leftStack.pop());
                this.movingMode = 1;
            }
        }else if(this.leftStack.size() == 0) {
            while(this.rightStack.size() != 0) {
                this.movingStack.push(this.rightStack.pop());
                this.movingMode = 2;
            }
        }
    }
    
    private void partionStacks() {
        this.createMovingStack();
        
        int size = movingStack.size();
        if(this.movingMode == 1) {
            this.partition(size/2, stack); // hier müssen die Stacks in richtiger Reihenfolge hin
            this.partition(size/2 + 1, stack);// hier auch
        }else if(this.movingMode == 2) {
            this.partition(size/2, stack); // hier müssen die Stacks in richtiger Reihenfolge hin
            this.partition(size/2 + 1, stack);// hier auch
        }
    }
    
    private void partition(int index, Stack<T> stack) {
        int i = 0;
        while(i < index) {
            stack.push(this.movingStack.pop());
            i++;
        }
    }
}
 
mihe7

mihe7

Top Contributor
L

LimDul

Top Contributor
Nur mal ein paar Gedanken-Fetzen

* Es ist eine Queue, wo ich an beiden Enden Dinge reintun kann, aber nur an einem Ende entnehmen kann
* Die soll mit Stacks umgesetzt werden

* Das heißt, es gibt auf jeden Fall zwei Stacks
* Der Stack für das "obere" Ende, wo ich auch entnehmen kann ist soweit ok. Wenn da was drauf tue und dann aus der Queue was entnehme, kommt das richtige Element raus
* Erst wenn dieser Stack leer ist und ich was entnehmen will, hab ich ein Problem
* Dann packe ich einfache den anderen Stack komplett rein, dadurch dreht sich dessen Reihenfolge um und ich bin wieder in einem konsistenten Zustand
 
Kirby.exe

Kirby.exe

Top Contributor
Nur mal ein paar Gedanken-Fetzen

* Es ist eine Queue, wo ich an beiden Enden Dinge reintun kann, aber nur an einem Ende entnehmen kann
* Die soll mit Stacks umgesetzt werden

* Das heißt, es gibt auf jeden Fall zwei Stacks
* Der Stack für das "obere" Ende, wo ich auch entnehmen kann ist soweit ok. Wenn da was drauf tue und dann aus der Queue was entnehme, kommt das richtige Element raus
* Erst wenn dieser Stack leer ist und ich was entnehmen will, hab ich ein Problem
* Dann packe ich einfache den anderen Stack komplett rein, dadurch dreht sich dessen Reihenfolge um und ich bin wieder in einem konsistenten Zustand
Ja genau das funktioniert aber nur wenn mann nur an einer Seite herausnehmen darf :) Sollte man aber wie bei Deque an beiden enden etwas rausnehmen dürfen, dann muss man wenn einer der beiden Stacks leer ist, den anderen gleichverteilen. Hier wüsste ich aber nicht wie ich das in guter Laufzeit machen soll :(
 
L

LimDul

Top Contributor
Ok, das hab ich überlesen.

Idee meinerseits für das gleichverteilen
3 Stacks
* Links
* Rechts
* Hilfs-Stack

Wenn einer der beiden Stacks (Links oder Rechts ist egal, hier mal als Beispiel Links), dann:
* Entferne die erste hälfte der Elemente aus dem Linken Stack und packe sie in den Hilfs-Stack (Reihenfolge dreht sich)
* Entferne die zweite Hälfte der Elemente aus dem Linken und packe sie in den Rechten Stack (Reihenfolge dreht sich) Das ehemal unterste Element des linken Stacks ist jetzt das oberste Element des rechten Stacks, was auch korrekt ist.
* Entferne alles aus dem Hilfs-Stack und packe es wieder in den linken Stack (Reihenfolge dreht sich wieder). Damit ist das oberste Element des linken Stacks wieder das gleiche wie vorher.

Schneller wüsste ich jetzt auch nicht, wie das rein mit Stacks gehen sollte
 
Kirby.exe

Kirby.exe

Top Contributor
Ok, das hab ich überlesen.

Idee meinerseits für das gleichverteilen
3 Stacks
* Links
* Rechts
* Hilfs-Stack

Wenn einer der beiden Stacks (Links oder Rechts ist egal, hier mal als Beispiel Links), dann:
* Entferne die erste hälfte der Elemente aus dem Linken Stack und packe sie in den Hilfs-Stack (Reihenfolge dreht sich)
* Entferne die zweite Hälfte der Elemente aus dem Linken und packe sie in den Rechten Stack (Reihenfolge dreht sich) Das ehemal unterste Element des linken Stacks ist jetzt das oberste Element des rechten Stacks, was auch korrekt ist.
* Entferne alles aus dem Hilfs-Stack und packe es wieder in den linken Stack (Reihenfolge dreht sich wieder). Damit ist das oberste Element des linken Stacks wieder das gleiche wie vorher.

Schneller wüsste ich jetzt auch nicht, wie das rein mit Stacks gehen sollte
Schneller geht es glaube ich auch nicht :) Müsste O(n) sein und armortisiert dann O(1) :)
 
Kirby.exe

Kirby.exe

Top Contributor
Alsooo ich habe das nun wie folgt gemacht:
Java:
private void partionElements(Stack<T> currentFull, Stack<T> currentEmpty) {
        int i = 0;
        while(currentFull.size() != 0 && i < currentFull.size()/2) {
            this.movingStack.push(currentFull.pop());
            i++;
        }
        while(currentFull.size() != 0) {
            currentEmpty.push(currentFull.pop());
        }
        while(this.movingStack.size() != 0) {
            currentFull.push(this.movingStack.pop());
        }
}

Ich denke dass es richtig ist :)

Aufgerufen wird das ganze so:
Java:
public T popLeft() {
        if(this.leftStack.size() == 0 && this.rightStack.size() != 0) {
            this.partionElements(this.rightStack, this.leftStack);
        }
        
        if(this.leftStack.size() != 0) {
            size--;
            return this.leftStack.pop();
        }
        
        return null;
    }
    
    public T popRight() {
        if(this.rightStack.size() == 0 && this.leftStack.size() != 0) {
            this.partionElements(this.leftStack, this.rightStack);
        }
        
        if(this.rightStack.size() != 0) {
            size--;
            return this.rightStack.pop();
        }
        
        return null;
    }
 
Kirby.exe

Kirby.exe

Top Contributor
Ich hoffe Ihr könnt mir eben nochmal auf die Sprünge helfen :) Ich soll nun eine armortisierte Analyse für beide durchführen. Hierbei würde es gerne mit der Potenzialmethode versuchen, da diese wohl bei den meisten Problemen funktioniert.

Bei der Potenzialmethode wählt man sich ja eine Potenzialfunktion Phi somit ist Phi(D_i) das Potenzial der i-ten Operation. Ich verstehe aber nicht wie das z.B. bei der isEmpty() funktion ist...xD Was ist hier Phi(D_0) also das Startpotenzial ? Ich stehe hier noch ein wenig auf dem Schlauch :)
 
Kirby.exe

Kirby.exe

Top Contributor
Also ich habe folgendes herausgefunden:

Scheinbar sind alle Funktionen welche nichts an dem Zustand der Datenstruktur ändern irrelevant und haben immer O(1) armortisierte Kosten.

Für PushLeft habe ich nun armortisierte Kosten von O(1) heraus. Für mein Potenzialfunktion haben ich Phi = Left.size() + Right.size() gewählt.

Somit funktioniert PushRight Analog zu PushLeft. Hier ist mein "Beweis":

Code:
Sei S die Anzahl von Elementen welche bereits auf beiden Stacks zusammen liegt:

a_i = c_i + Phi(D_i) - Phi(D_{i-1})
    = 1 + (S+1) - S
    = 1 + 1 + S - S
    = 2

Somit hat PushLeft armortisierte Kosten von O(1).
Da PushRight analog zu PushLeft funktioniert hat dies ebenfalls
armortisierte Kosten von O(1).

Ich bin mir aber nicht ganz sicher ob das ganz richtig ist wie ich das hier mache :)
 

Oben