Queue mit einem Array implemetieren

[Mariexshhx]

Hey ich soll eine Queue mit einem Array implemtieren mit der Methode pop(), die die Laufzeit O(1) haben soll. Ich frage mich wie das möglich sein soll in dieser Worst Case Laufzeit

Meine pop Methode sieht im Pseudocode so aus ...

function pop()
    if empty()
        return // wenn A leer ist soll nix passieren
        
x=top()
    for(j=1 .... n-1)
        A[j-1]=A[j] // das wäre aber doch Laufzeit O(n-1)?

Hat jemand eine andere Idee für mich, um das erste Element zu löschen?

 

[LimDul]

Anstelle alles im Array zu verschieben, merk dir einfach den Index von top (und tail) und stell dir vor, das Array wäre rund. Sprich nach dem letzten Index geht es einfach wieder mit dem ersten weiter.

 

[Mariexshhx]

Anstelle alles im Array zu verschieben, merk dir einfach den Index von top (und tail) und stell dir vor, das Array wäre rund. Sprich nach dem letzten Index geht es einfach wieder mit dem ersten weiter.

Also muss ich nur A[0] auf A[1] setzen? Ich verstehe es noch nicht ganz

 

[KonradN]

Stell Dir sowas bildlich vor! Zeichne es Dir auf. Oder bau Dir visuelle Beispiele!

Du kannst Dir das Array als eine Art Regal vorstellen. Und das steht in einem Raum. Der Raum hat einen Eingang und einen Ausgang.

Immer wenn Dir jemand eine Kiste beim Eingang geben will, musst Du diese entgegen nehmen und im Regal unter stellen.
Immer wenn jemand am Ausgang eine Kiste haben will, dann musst Du eine Kiste aus dem Regal nehmen und ihm geben.

Nun müssen die Kisten aber in genau der Reihenfolge ausgegeben werden, wie Du diese bekommen hast. Und Du hast für irgend welches umsortieren keine Zeit.

Überlege Dir einmal, ob Du das irgendwie hin bekommen kannst.

Wenn Du Probleme hast, da eine Lösung zu finden: Stell Dir vor, du hast nicht ein Regal sondern Du hast mehrere Stellplätze auf dem Boden im Kreis angeordnet sind. Vielleicht gelingt es Dir ja da?

 

[Mariexshhx]

Stell Dir sowas bildlich vor! Zeichne es Dir auf. Oder bau Dir visuelle Beispiele!

Du kannst Dir das Array als eine Art Regal vorstellen. Und das steht in einem Raum. Der Raum hat einen Eingang und einen Ausgang.

Immer wenn Dir jemand eine Kiste beim Eingang geben will, musst Du diese entgegen nehmen und im Regal unter stellen.
Immer wenn jemand am Ausgang eine Kiste haben will, dann musst Du eine Kiste aus dem Regal nehmen und ihm geben.

Nun müssen die Kisten aber in genau der Reihenfolge ausgegeben werden, wie Du diese bekommen hast. Und Du hast für irgend welches umsortieren keine Zeit.

Überlege Dir einmal, ob Du das irgendwie hin bekommen kannst.

Wenn Du Probleme hast, da eine Lösung zu finden: Stell Dir vor, du hast nicht ein Regal sondern Du hast mehrere Stellplätze auf dem Boden im Kreis angeordnet sind. Vielleicht gelingt es Dir ja da?

Stell Dir sowas bildlich vor! Zeichne es Dir auf. Oder bau Dir visuelle Beispiele!

Du kannst Dir das Array als eine Art Regal vorstellen. Und das steht in einem Raum. Der Raum hat einen Eingang und einen Ausgang.

Immer wenn Dir jemand eine Kiste beim Eingang geben will, musst Du diese entgegen nehmen und im Regal unter stellen.
Immer wenn jemand am Ausgang eine Kiste haben will, dann musst Du eine Kiste aus dem Regal nehmen und ihm geben.

Nun müssen die Kisten aber in genau der Reihenfolge ausgegeben werden, wie Du diese bekommen hast. Und Du hast für irgend welches umsortieren keine Zeit.

Überlege Dir einmal, ob Du das irgendwie hin bekommen kannst.

Wenn Du Probleme hast, da eine Lösung zu finden: Stell Dir vor, du hast nicht ein Regal sondern Du hast mehrere Stellplätze auf dem Boden im Kreis angeordnet sind. Vielleicht gelingt es Dir ja da?

Bei dem Kisten im Regal könnte ich wenn ich die vordeste Kiste wegnehme den Anfang also top einfach um eins nach rechts verschieben ? Aber beim Array geht das ja nicht oder ? Muss ich die Positionen nicht überschreiben ?

 

[KonradN]

Stell es Dir vor. Ich sehe Kisten, ich sehe das Regal. Ich sehe keine "Positionen" oder "top" oder so. Wenn Du bei der bildlichen Vorstellung irgend etwas zusätzlich brauchst, dann beschreibe es!

Vergiss irgendwelche Programmier Dinge. Du musst die Problematik verstehen und eine Lösung finden. Denn es scheint ganz offensichtlich noch Probleme beim Verständnis zu geben. Ansonsten wäre mit der Antwort von @LimDul der Thread beendet gewesen.

 

[Mariexshhx]

Stell es Dir vor. Ich sehe Kisten, ich sehe das Regal. Ich sehe keine "Positionen" oder "top" oder so. Wenn Du bei der bildlichen Vorstellung irgend etwas zusätzlich brauchst, dann beschreibe es!

Vergiss irgendwelche Programmier Dinge. Du musst die Problematik verstehen und eine Lösung finden. Denn es scheint ganz offensichtlich noch Probleme beim Verständnis zu geben. Ansonsten wäre mit der Antwort von @LimDul der Thread beendet gewesen.

wenn ich die vorderste Kisten wegnehme ist die Kiste danach dann mein Anfang

 

[Neumi5694]

Krümme dein Regal mal nach hinten, bis es "fast" einen Kreis ergibt. Dann stell außen einen Stuhl (mit Rollen) hin, der deine aktuelle Position beziechnet. Wenn du die nächste Position willst, bewegt der sich einen Platz nach rechts. Sobald er das offene Ende deines Fast-Kreises erreicht, springt er im nächsten Schritt an den Anfang des Kreises.
Ein zweiter Stuhl bezeichnet die Stelle, an der du eine neue Kiste lagerst, verhält sich genauso.

Das Problem bei dem Arraymodell (egal ob mir verschieben oder Index weiterdrehen) ist, dass es irgendwann auch mal voll sein kann, wenn du nicht ein sehr langes verwendest. Mit der Indexverschiebung würde das passieren, wenn der Auffüllindex den Abarbeitungsindex überholt.

 

[Mariexshhx]

Krümme dein Regal mal nach hinten, bis es "fast" einen Kreis ergibt. Dann stell außen einen Stuhl (mit Rollen) hin, der deine aktuelle Position beziechnet. Wenn du die nächste Position willst, bewegt der sich einen Platz nach rechts. Sobald er das offene Ende deines Fast-Kreises erreicht, springt er im nächsten Schritt an den Anfang des Kreises.
Ein zweiter Stuhl bezeichnet die Stelle, an der du eine neue Kiste lagerst, verhält sich genauso.

Das Problem bei dem Arraymodell (egal ob mir verschieben oder Index weiterdrehen) ist, dass es irgendwann auch mal voll sein kann, wenn du nicht ein sehr langes verwendest.

ich hatte überlegt einen Zeiger top zu verwenden, der auf auf den Anfang der Queue zeigt. Also ist am Anfanf =0, wenn wir nun das vorderste Element löschen wir top=1 und A[top] wird bei top zurückgegeben... nur wirklich gelöscht wird ja jetzt das Element bei A[0] nicht. Es wird halt nicht mehr beachtet..Quasi so

function pop()
    if empty()
        return // wenn A leer ist soll nix passieren
       
x=top()
t++ //Variable die den Anfang der Queue anzeigt 
return x

 

[KonradN]

ich hatte überlegt einen Zeiger top zu verwenden, der auf auf den Anfang der Queue zeigt. Also ist am Anfanf =0, wenn wir nun das vorderste Element löschen wir top=1 und A[top] wird bei top zurückgegeben... nur wirklich gelöscht wird ja jetzt das Element bei A[0] nicht. Es wird halt nicht mehr beachtet..Quasi so

Ja, das entspricht genau der Idee von @LimDul. Ggf. musst Du noch überlegen, dass Du Dir auch das tail merken musst, damit Du die Situationen erkennen kannst:

• Regal voll -> dann kannst Du keine Kiste einstellen
• Regal leer -> dann kannst Du keine Kiste mehr entnehmen

 

[Neumi5694]

Eine Versschiebeoperation klappt natürlich auch, Java bietet dafür ja eine recht praktische Methode an.
Insgesamt könnte das aber die einfachere Methode sein, als einen Ringpuffer zu verwenden, hier musst du nur die Länge des Arrays im Auge behalten, um zu wissen, ob noch weitere Elemente hinzugefügt werden können.

Dann könnte das so oder so ähnlich funktionieren (Ich nehme nicht für mich in Anspruch, keinen Fehler bei den Indizes gemacht zu haben, hab's nicht getestet).
Methodennamen hab ich mal frei gewählt, nicht geschaut, ob da ein Interface was vorschreibt.

public final synchronized Optional<Thing> fetch() {
    if (hasElements()) {
        Collections.rotate(Arrays.asList(values).subList(0, nElements), 1);
        return Optional.of(values[--nElements]);
    } else {
        return Optional.empty();
    }
}

public final synchronized boolean add(Thing t) {
  if (hasCapacity()) {
    values[nElements++] = t;
    return true;
  } else {
    return false;
  }
public final synchronized boolean hasElements() {
  return nElements > 0;
}
public final synchronized boolean hasCapacity() {
  return nElements < values.length();
}
private Thing[] values = new Things[maxcapacity];
private int nElements = 0;
}

 

[Mariexshhx]

Ja, das entspricht genau der Idee von @LimDul. Ggf. musst Du noch überlegen, dass Du Dir auch das tail merken musst, damit Du die Situationen erkennen kannst:

• Regal voll -> dann kannst Du keine Kiste einstellen
• Regal leer -> dann kannst Du keine Kiste mehr entnehmen

ich hatte mir überlegt eine Variable anzulegen, die die Elemente in dem Array zählt also immer wenn, ich Element eingefügt wird wird die Zählvariale erhöht und wenn die = A.length ist, ist das Array ja voll, wenn ich hier richtig überlege und wenn eins entfernt wird, wird die Varibale um 1verringert

 

[KonradN]

ich hatte mir überlegt eine Variable anzulegen, die die Elemente in dem Array zählt also immer wenn, ich Element eingefügt wird wird die Zählvariale erhöht und wenn die = A.length ist, ist das Array ja voll, wenn ich hier richtig überlege und wenn eins entfernt wird, wird die Varibale um 1verringert

Das wäre auch eine Möglichkeit - dann bräuchtest Du nur das top.

 

[temi]

ich hatte mir überlegt eine Variable anzulegen, die die Elemente in dem Array zählt also immer wenn, ich Element eingefügt wird wird die Zählvariale erhöht und wenn die = A.length ist, ist das Array ja voll, wenn ich hier richtig überlege und wenn eins entfernt wird, wird die Varibale um 1verringert

Aber ist eine Queue nicht FIFO? Was du beschreibst, klingt nach LIFO

 

[Neumi5694]

Aber ist eine Queue nicht FIFO? Was du beschreibst, klingt nach LIFO

Zum Befüllen reicht's. Mit dieser Methode muss man halt noch die Liste bei einer der Operationen rotieren.


Das hätte man dem sagen sollen, der unser Postsystem entwickelt hat. Entweder das, oder er hielt das nicht für besonders wichtig.

 

[temi]

Mit dieser Methode muss man halt noch die Liste bei einer der Operationen rotieren.

die die Laufzeit O(1) haben soll

 

[Neumi5694]

Na dann eben die Ringlösung mit 2 Zeigern, wurde ja auch schon rauf und runter beschrieben.