Stack erweitern mit neuem Array falls der alte voll ist!?

[Proxy]

Schönen Guten Tag die Damen und Herren,

meine Frage ist, wenn der Stack nun voll ist und ich ihn in der Push-Methode erweitern möchte, ich dann auch dem Konstruktor etwas mit geben muss oder kann ich gleich in der Methode ein neues Array erstellen lassen ?
Falls es in der Methode ist, kann mir da jemand einen Tipp geben....stehe bisschen auf dem Schlauch. 🙂

Vielen Dank schonmal. 🙂

public class IntegerStack {
    
    
    private int storage [];
    private int heigth;
    private int top;
    
    
    public IntegerStack( int heigth) {
        
        storage = new int [heigth];
        this.heigth = heigth;
        top= -1;
        
    }
  
    public void push ( int value) {
        if (top != heigth - 1) {
            storage[++top]=value;
            
        } else {
            if ( storage[top]==heigth -1) {
                    ?????????
                
                }
            }
    }
        
        
    
    
    public int pop() {
        if (!empty()) {
            return storage[top--];
        }
            return -1;                // wir wissen Stack == leer!!!!   
    }
    
    public boolean empty() {
        
        return top == -1;
            
    }
    
    public int top() {
        if (!empty()) {
            return storage[top];
        }return -1;
        
        
    }

 

[KonradN]

Überlege Dir den Algorithmus erst einmal mit Worten. Stell es Dir ggf. Bildlich vor. Du hast einen kleinen Zettel auf den Du Dinge schreibst. Nun ist der Zettel voll: Was kannst Du machen?

Du willst einen größeren Zettel nehmen? Was musst Du dann machen? Auf dem kleinen Zettel steht ja bereits etwas, das Du nicht verlieren willst.

Also immer erst ein Worten sauber formulieren, was Du machen willst. Fang nicht mit Code an! Da konn nur Müll bei raus kommen (sorry! Aber was soll das `if ( storage[top]==heigth -1) [CODE]? Was hast Du Dir da gedacht?) Und als kleinen Tipp am Rande: Überlege Dir, ob Du den postdecrement bzw. preincrement Operator wirklich so nutzen willst. Das ist zwar schön kurz, aber von der Lesbarkeit ist dies immer relativ schwer lesbar. Und da sieht man nicht wirklich, was richtig ist. Muss es nun ```storage[++top]=value;[/CODE] oder storage[top++]=value;`` sein? Bzw. die Frage: Siehst Du den Fehler, wenn die falsche Variante da steht?
Es macht aus meiner Sicht Sinn, dass man das so schreibt, dass es wirklich gut zu lesen ist.

Oder einfach mal die Worte von Grady Booch:

Clean code is simple and direct.
Clean code reads like well-written prose.
Clean code never obscures the designer’s intent but rather is full of crisp abstractions and straightforward lines of control.

 

[Proxy]

Vielen Dank für die schnelle Antwort.

if ( storage[top]==heigth -1)

War nur ne Überlegung 😀

Ich versuchs mal, auf dem Blatt. Ich werde es in der Methode gleich erweitern.

 

[KonradN]

Ja, aber in Code überlegen ist immer blöd, wenn man da noch nicht so ganz sicher ist. Du hast ja zwei unterschiedliche Dinge. Einmal den Inhalt von dem Stack. Und zum anderen eine Größe vom Stack. Du vergleichst da also Äpfel mit Birnen. Das ist in der Regel nicht richtig. (WObei es natürlich durchaus richtig sein kann.... Man kann immer Situationen erschaffen, wo Du Äpfel mit Birnen vergleichst: Du kriegst eine LKW Ladung Äpfel und eine LKW Ladung Birnen und dann hast Du die Aufgabe, 1 Apfel und 1 Birne auszusuchen, die sich möglichst ähnlich sind.)

Oder auf das Beispiel mit dem Blatt Papier zurück zu kommen: Du willst ja nicht schauen, ob unten rechts in der Ecke steht, wie groß das Papier ist. Also das wäre ja etwas wie prüfen, ob unten rechts auf dem Din A4 Blatt "A4" steht. Evtl. macht so eine Prüfung irgendwo Sinn (Auch hier kann man sich Situationen aus den Fingern saugen: Du willst als Hersteller von Papier unten Rechts die Größe stehen haben. Also wird die QA Abteilung prüfen: Steht da überall auch wirklich die korreke Größe?).
Aber so etwas haben wir hier ja nicht.

Aber generell: Ja, die Idee dann ein neues, größeres Blatt zu nehmen ist gut! Du musst halt nur schauen, wie Du die Daten behalten kannst.

Ganz nebenbei: Das was Du da gerade baust, ist auch im Java Framework zu finden. Die ArrayList arbeitet auch so: Man hat intern ein Array in dem die Daten gespeichert werden. Ist das Array voll, dann wird ein größeres Array genommen (und natürlich noch etwas mehr gemacht damit) um halt die Daten wirklich speichern zu können.

 

[Proxy]

Vielen Dank für die Antwort.

Meine Frage war halt grundsätzlich, ob ich auch dem Konstruktor, da was mit geben muss oder nicht, weil ich ein wenig auf dem Schlauch stand. 😀

Aber ich habs jetzt schon raus.

public void push ( int value) {
        
    if (storage.length == heigth) {
        int []copy = new int[storage.length+10];
        for (int i =0; i!=heigth; i++) {
            copy[i]= storage[i];
        }storage=copy;
    }storage[++top]= value;

 

[KonradN]

Ja genau. Und Du hast es richtig gemacht - der Konstruktor braucht diesbezüglich keine weiteren Informationen.

Dein Code ist somit schon eine super Lösung.

Evtl. paar Anmerkungen:

• Bei so eine for Schleife, die ein Array durchgeht: Da wäre etwas wie i < heigth üblicher. Dein != macht aber unter dem Strich auch nichts anderes, aber mit dem < wird es in der Zähl Schleife eifnach etwas deutlicher da es ja eine Aussage wäre ähnlich "zähle so lange wie du kleiner als.... bist"
• Eine schwere Frage ist immer, mit welcher Strategie man vorgeht. Das einzig wichtige ist natürlich: Es muss mindestens um 1 Element vergrößert werden. Teilweise findet man Ansätze wie: Wir packen immer 50% und mind. 1 Element drauf. EInfach um zu vermeiden, dass man zu oft das Array vergrößern muss.

Mit dem +50% hätte man ein schnelles Anwachsen bei großer Anzahl an Elementen.
Das aber wirklich nur als Gedanken zu der Lösung - das ist keine Kritik! Deine erarbeitete Lösung ist korrekt und gut!