Eigene Stack Klasse

[sh33p]

Ich habe folgende Stack-Klasse,die auf einem Array basiert:

public final class Stack {

 private int count; // aktuelle Zahl der Elemente - 1
 // Index des obersten Elements

 private int[] a = new int[10];


 public Stack () { // Konstruktor, erzeugt den leeren Stapel
 count = -1;
 }


 public int top() { // liefert das oberste Element
 // Vorbedingung: Stapel nicht leer
 if (count<=9 && count>=0) {
 return a[count];
 } else
 return -999;
 }

 //  legt Element ab
 public void push(final int x){
 // Vorbedingung: Stapel nicht voll
 if (count<9) {
 
 count++;
 a[count] = x;
 }
 }
 public void pop(){ // veraendert Stapel-Zustand: entfernt oberstes Element
 // Vorbedingung: Stapel nicht leer
 if (count>=0) {
 count--;
 }
 }
 }
 
 // Klasseninvariante: count darf nicht außerhalb -1 <= count <= 9 liegen

Nun soll ich ein Testklasse mit main funktion schreiben, mit Drei push-pop-top-Folgen der Laenge > 5 unter Einhaltung der Stack- Invariante und Zwei nichtleere push-pop-top-Folgen mit Verletzung der Stack-Invariante.

Die Stack Invariante lautet ja in dieser Implementierung: count darf nicht außerhalb -1 <= count <= 9 liegen.

Was ist bitte mit 3 push-pop-top folgen der Länge 5 gemeint??

public class StackTB {

  public static void main(String[] args) {
  // 3 push top -pop- top folgen der laenge 5??
  Stack s1 = new Stack();
  s1.push(2); //Oben drauflegen
  s1.pop(); // entfernen
  s1.top(); //lesen
  s1.push(3);
  s1.pop();
  
  s1.push(4); //Oben drauflegen
  s1.pop(); // entfernen
  s1.top(); //lesen
  s1.push(5);
  s1.pop();
  
  
  s1.push(4); //Oben drauflegen
  s1.pop(); // entfernen
  s1.top(); //lesen
  s1.push(5);
  s1.pop();
  
  }
}

 

[Marcinek]

Genau sowas ist es

 s1.push(4); //Oben drauflegen
  s1.pop(); // entfernen
  s1.top(); //lesen
  s1.push(5);
  s1.pop();

 

[sh33p]

und das 3 mal hintereinander ? ???:L

 

[Landei]

Ja.

Übrigens würde ich bei einem leerem Stack in top() und pop() eine Exception werfen (NoSuchElementException würde sich anbieten)

 

[sh33p]

danke.

ich habe noch eine weitere frage. wie kann ich den Stack dynamisch machen?D.h wenn festgestellt wird,das das Array voll wird-> Speicherplatz verdoppeln.
Ist eigentlich nur mit einer ArrayList möglich oder?
Müsste ich natürlich alles auf eine Arraylist umbauen..

 

[Ein Keks]

eine ArrayList benutzt intern auch ein array (daher der name)
du musst einfach ein neues array mit der neuen größe erstellen und den inhalt des alten reinkopieren (z.B mit System.arraycopy)

 

[Marcinek]

im sinne der übung würde ich versuchen es ohne die arrayliste machen.

weil man sonst auch ein Stack nutzen kann

Mit nichten benutzt ArrayList intern ein Array (Sorry, da war ich in einem falschen Universum) - Siehe posting unten...

 

[sh33p]

ok danke

 

[maki]

...
Mit nichten benutzt ArrayList intern ein Array -.-:autsch:

Sicherlich nutzt ArrayList intern ein Array, steht sowohl in der Doku als auch im Quellcode

 

[sh33p]

ich habe jetzt versucht die Verdoppelungsstrategie zu implementieren. Nur es klappt noch nicht ganz.wo liegt der fehler?

[Java]

private int count; // aktuelle Zahl der Elemente -1

private int[] a = new int[10]; // Ablageplatz fuer die Elemente
private int[] b = new int[count*2]; // Zweites Array zum verdoppeln

// a[0]...a[count] sind die gestapelten Elemente
// a[count] ist das oberste, a[0] das unterste
// INV: -1 <= count <= 9

public StackDYN() { // Konstruktor, erzeugt den leeren Stapel
count = -1;
}

public int top(){ //Oberste Element lesen


if(count > a.length)
return b[count];
else
return a[count];


}
public void push(final int x) { //Oberste Element drauflegen
if(count >9){

System.arraycopy(a,0,b,0,b.length);
}

if(count < 9){
count++;
a[count] = x;
}
}

public void pop() { // Oberste Element entfern
try{
if (count >= 0)
count--;
if(count <-1)
throw new Exception();
}catch(Exception z){
}
}
}
[/code]

 

[Marcinek]

1. Wenn du eine exeption wirst und sie direkt fängst, dann kannst du sie dir schenken

2. Du musst nur ein tmp array haben, und wenn count über aktuelle size hinweggeht, dann wird der aktuelle Stand in den neuen kopiert und dann die referenzen vertauscht, so dass du immer mit nur einem array arbeitest.

3. man würde im Konstruktor eine start kapazität angeben

4. so statische sachen wie count < 9 kann man auch nimma verwenden

 

[sh33p]

ok und wie mache ich das mit dem tmp array?
ich hol mir die kapazität durch eingabe über die konsole.wenn die kapazität > 10 ist, dann neues anlegen?
wie gehts dann weiter?

 

[Marcinek]

if(count > a.length) {
    int[] b = new int[a.lenth * 2];
   copy a nach b
   b = a;
}

a[count] = x;

 

[sh33p]

public int top(){     //Oberste Element lesen


   if(count < 9){
    return a[count];
   }else
   return b[count];

}
 public void push(final int x)  {   //Oberste Element drauflegen
 if(count >9){

   System.arraycopy(a,0,b,0,b.length);
   b = a;
}

a[count] = x;


}

jetzt hagelts eine indexoutofbounds -1 exception^^

 

[Marcinek]

ja ich sehe auch wo...

und (top) muss man auch noch mal überdenken

Aber das wirst du schon schaffen...

 

[sh33p]

so die -1 exception hab ich weg..kriege es aber einfach nicht gebacken,das top dann auf den richtigen index zugreift, wenn es muss..bitte helft mir :bahnhof:

 

[sh33p]

hilfe ! ;(

 

[Final_Striker]

Was soll dieses zweite b array?

Erst wenn das erste voll ist, erzeugst du ein neues z.B. mit doppelter Größe
kopierst die Inhalte von a rein

int temp = new int[a.length * 2];
// Inhalte kopieren
a = temp;

 

[Landei]

Für einen unbeschränkt wachsenden Stack bietet sich eine einfach verkettete unveränderliche Liste an: http://www.java-forum.org/blogs/landei/104-einfach-verkettete-listen-veraenderlich.html

De-fakto ist so eine Liste schon eine Art Stack. Damit spart man sich das Umkopieren und das Hantieren mit Array-Indizes. Durch die Referenzen verbraucht man allerdings mehr Speicher, was aber nur bei großen Datenmengen wirklich ins Gewicht fällt.

 

[sh33p]

ok.aber wie differenze ich das in der top() methode?

Wenn ich das ursprüngliche array (<9 werte) habe,muss ich auf das zugreifen, und bei dem 2. array (bei > 9) werte auf das..wie setze ich das in quellcode um?

 

[Marcinek]

Du hast doch nur ein Array, was willst du da differenzieren?

 

[sh33p]

ich weiß einfach nur nicht,wie ich die top methode realisieren soll..

 

[Marcinek]

return a[count];

 

[sh33p]

funktioniert nicht.
ich möchte ja mit top auch auf das temp array zugreifen,wenn a voll ist.

 

[Marcinek]

warum funktioniert es nicht und warum möchtest du auf das temp zugreifen? - Meine Glaskugel scheint ein wenig defekt zu sein...

Weißt du, was temporär (temp) bedeutet?

Male dir ein Stack auf und daneben dein count und wie sich das ändert.

Dann siehst du die Lösung.


---
Hast du ein Java Buch schon mal angeschaut??

Ansonsten kann ich dir auch Nachhilfe (kostenpflichtig) anbieten.

 

[Landei]

Ich bin immer noch der Meinung, dass es ohne Array besser geht...

import java.util.Iterator;
import java.util.NoSuchElementException;

public class Stack<E> implements Iterable<E> {
    private Node<E> tos = new Nil<E>();

    public boolean isEmpty() { return tos.isEmpty(); }
    public void push(E e) { tos = tos.push(e); }
    public E top() { return tos.top(); }
    public E pop() {
        E e = tos.top();
        tos = tos.pop();
        return e;
    }

    public Iterator<E> iterator() {
        return new Iterator<E>(){
            Node<E> node = tos;
            public boolean hasNext() {  return ! node.isEmpty(); }
            public E next() {
                E e = node.top();
                node = node.pop();
                return e;
            }
            public void remove() {
                throw new UnsupportedOperationException("Not supported yet.");
            }
        };
    }

    private static abstract class Node<E> {
        abstract E top();
        abstract Node<E> pop();
        abstract boolean isEmpty();
        Cons<E> push(E f) { return new Cons(f, this); }
    }

    private static class Cons<E> extends Node<E> {
        private final E e;
        private final Node<E> next;
        private Cons(E e, Node<E> next) {
            this.e = e;
            this.next = next;
        }
        public E top() { return e; }
        public Node<E> pop() { return next; }
        public boolean isEmpty() { return false; }
    }

    private static class Nil<E> extends Node<E> {
        public E top() { return null; }
        public Node<E> pop() { throw new NoSuchElementException("Stack empty!"); }
        public boolean isEmpty() { return true; }
    }
}

 

[ARadauer]

Kommt mir bekannt vor: http://www.java-forum.org/java-basics-anfaenger-themen/107866-exceptions-push-pop-stack.html

Ok:
1. Verwirf deine "Verdopplungs Strategie". Wenn dein array zu klein wird, machst du dir ein temp, das doppelt so groß ist, kopierst um und weißt temp deinem ursprünglichen zu.
Die Idee dass, wenn das erste voll ist du mit dem zweiten weiterarbeitest ist. a) falsch b) blödsinn ;-)

2. Räum deinen Code mal auf. Sauber formatieren, einrücken, unnötiges herumgebastle raus werfen.

Funktionierts dann immer noch nicht: poste ihn im anderen Thread, dann helf ich dir. Is wahrscheinlich dann nur noch eine Kleinigkeit...