Du verwendest einen veralteten Browser. Es ist möglich, dass diese oder andere Websites nicht korrekt angezeigt werden. Du solltest ein Upgrade durchführen oder ein alternativer Browser verwenden.
Hi,
Wie kann ich rausfinden ob ein Array der von beiden Seiten mittels Pop Daten entfernt bekommen kann leer ist ? Nach dem Kellerprinzip Lifo hätte ich natürlich einfach this.current-1 gecheckt um zu testen ob mein Array leer ist. Nun hatte ich überlegt zu überprüfen this.current-1 && this.array.length==this.array.length+1.
Lösche ich aber beidseitig jeweils ein Element, dann wäre hierfür ja mein Array leer was ja nicht stimmt. Muss ich hierfür das mittlere Element auf Existenz überprüfen ? und wenn ja wie ?
Es geht um die DoubleEndedque
Also du würfelst hier gewaltigst Begriffe durcheinandern:
Push, Pop: Zugriffsmethoden auf einen Stack
Ein Array hat immer eine fixe größe, du kannst keine Daten aus einem Array "entfernen". Du kannst sie nur überschreiben oder ein neues Array anlegen.
Einen Stack und ein Array sind zwar beide Datenstrukturen, haben sonst aber ungefähr gar nichts gemeinsam. Was versuchst du denn eigentlich zu machen? Was muss deine "DoubleEndedque" können?
Mein Code bisher. Wobei das mimt Empty noch nicht geklärt ist
Java:
public class Deque {
/*
* Verweis auf aktuellen Index und lege Array an
*/
int current;
int[]store;
/*
* Konstruktor mit maximaler größe als Parameter
*/
Deque(int maxzise){
this.store=new int[maxzise];
this.current=-1;
}
/*
* Liefere true wenn Deque leer ist
* Es muss zweiseitig überprüft werden
*/
boolean isEmpty(){
return this.current==-1 && this.store.length==this.store.length+1 ;
}
boolean isFull(){
return this.current ==(this.store.length-1);
}
/*
* Füge Wert hinten in die Deque ein
*/
void push(int value){
this.store[++this.current] = value;
}
}
Hm, du brauchst du mindestens mal zwei "current" pointer. Einen für das vordere Ende und einen für das hintere Ende, oder nicht?
Wenn
Code:
current1 + 1 == current2
gilt, dann ist die Deque leer. Wenn
Code:
current1 == 0
und
Code:
current2 == length - 1
dann ist die Deque an beiden Seiten voll und es können keine weiteren Daten hinzugefügt werden.
Zusätzlich hast du noch die beiden Methoden push() und put() zum hinzufügen von Daten sowie pop() und get() zum entfernen der Daten vom jeweiligen Ende.
Nein, das passt doch überhaupt nicht. du setzt damit current1 auf -1, wie soll das denn passen?
Wenn du nen Array der Länge 11 hast, dann müssen deine Pointer am Anfang auf 5 und 6 zeigen.
Als Anregung (bei ungerader Länge):
Math.floor(länge / 2)
Math.ceil(länge / 2)
Zeichne dir das auf nem Blatt papier auf wie der Anfang ausschaut. Was passiert beim Hinzufügen eines Elements, was passiert beim Löschen, was passiert in der Mitte, was passiert an den Rändern.
Ich soll eine Klasse Deque schreiben mit einer Datenstruktur ähnlich des Stacks oder einer Schlange. Der Unterschied besteht hier darin ,dass die Daten an beiden Enden gelesen/eingefügt und entfernt werden können.
Um das umzusetzen muss ich ja von der Mitte meines Speichers ausgehen um überhaupt überprüfen zu können ob er z.b leer ist. Nun weis ich grad nicht wie ich mit 2 mittlere Indexe baue.
Ist das machbar ?
Idee war wie vom Landei beschrieben
Ich weis schon was eine Deque ist, die Realisierung mit Arrays finde ich nur seltsam weil entgegen dem Prinzip der Liste. Besonders für eine Übungsaufgabe.
laut Wiki muss ich mit einer Doppel verkettete Liste arbeiten oder mit Feldern und Indizes.
Habe allerdings noch keine Vorstellung wie ich vorgehen soll. ADTs wie Schlange,Keller sind mir bekannt. Dies scheint etwas komplizierter..
Hat jemand nen Vorschlag wie ich das in meinen Code bastle ?
Würde gerne mit den Indizes Arbeiten
Hier ein Implementierungsvorschlag von mir, wobei ich aus didaktischen Gründen ein paar Zeilen weggelassen habe...
Java:
import java.util.NoSuchElementException;
public class Dequeue<T> {
private static class Node<T> {
private Node<T> prev;
private Node<T> next;
private final T value;
public Node(T value, Node<T> prev, Node<T> next) {
this.prev = prev;
this.next = next;
this.value = value;
}
}
private int size = 0;
private Node<T> first = null;
private Node<T> last = null;
public int getSize() {
return size;
}
public boolean isEmpty() {
return size == 0;
}
public void pushFirst(T value) {
if (isEmpty()) {
???
} else {
???
}
size++;
}
public void pushLast(T value) {
???
}
public T peekFirst() {
if (isEmpty()) {
throw new NoSuchElementException();
}
return first.value;
}
public T peekLast() {
???
}
public T popFirst() {
if (isEmpty()) {
throw new NoSuchElementException();
}
T value = first.value;
???
return value;
}
public T popLast() {
???
}
}
Nur noch die ??? passend ersetzen. Aufmalen der doppelt verketteten Liste hilft übrigens ungemein.