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:
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:
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++;
}
}
}