# Eigene Stack Klasse



## sh33p (23. Okt 2010)

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 (23. Okt 2010)

Genau sowas ist es


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


----------



## sh33p (23. Okt 2010)

und das 3 mal hintereinander ? ???:L


----------



## Landei (23. Okt 2010)

Ja. 

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


----------



## sh33p (23. Okt 2010)

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 (23. Okt 2010)

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 (23. Okt 2010)

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 (23. Okt 2010)

ok danke


----------



## maki (23. Okt 2010)

Marcinek hat gesagt.:


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


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


----------



## sh33p (23. Okt 2010)

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 (23. Okt 2010)

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 (23. Okt 2010)

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 (23. Okt 2010)

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

a[count] = x;
```


----------



## sh33p (23. Okt 2010)

```
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 (23. Okt 2010)

ja ich sehe auch wo...

und (top) muss man auch noch mal überdenken

Aber das wirst du schon schaffen...


----------



## sh33p (23. Okt 2010)

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 (23. Okt 2010)

hilfe ! ;(


----------



## Final_Striker (23. Okt 2010)

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 (23. Okt 2010)

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 (23. Okt 2010)

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 (23. Okt 2010)

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


----------



## sh33p (25. Okt 2010)

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


----------



## Marcinek (26. Okt 2010)

return a[count];


----------



## sh33p (28. Okt 2010)

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


----------



## Marcinek (28. Okt 2010)

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 (28. Okt 2010)

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 (29. Okt 2010)

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...


----------

