# Stack implementieren



## kurtisblow (27. Mrz 2012)

Hallo, ich bin dabei einen Stack zu implementieren, welcher einen JUnit4 Test erfüllen sollte.

Ich habe eigentlich alles fertig, jedoch wird der Test nicht erfüllt. Ich sehe einfach den Fehler nicht ein, vielleicht kann mir da jemand helfen:




```
package u4a1;

import java.util.EmptyStackException;

/**
 * Dynamically growing stack.
 */
public class Stack {
	private int[] buffer;
	private int size;

	/**
	 * Creates a new stack
	 * 
	 * @param capacity the initial capacity of the stack
	 */
	public Stack(int capacity) //Constructor
	{
		size = 0;
		buffer = new int [capacity];
	}

    /**
	 * Converts stack to a string representation.
	 * 
	 * @return A ", "-separated list of the numbers, enclosed in square brackets. Bottom numbers come first. 
	 */
	public String toString() //convert Stack toString
	{
		String stackString = "";
		for (int i = 0; i<size;i++)
		{
			stackString = stackString + buffer[i]  + ", "; 
		}
		return stackString;
	}
	
	/**
	 * Doubles the capacity of the stack.
	 * 
	 * Copies all objects to a new buffer of doubled size.
	 */
	private void grow()
	{
		int [] copyBuffer = new int [2*buffer.length];
		for (int i = 0; i<size;i++)
		{
			copyBuffer[i] = buffer[i];
		}
		buffer = copyBuffer;		
	}

	/**
	 * Pushes a number onto the top of this stack.
	 * 
	 * Grows the stack if necessary.
	 * 
	 * @param number the number to be pushed onto this stack. 
	 */
	public void push(int number)
	{
		if (size >= buffer.length)
		{
			grow();
			size = size + 1;
			buffer[size] = number;
		}
		else 
		{
			size = size + 1;
			buffer[size] = number;
			
		}
	}
	
	/**
	 * Removes the number at the top of this stack and returns it as the value of this function. 
	 * 
	 * @return The number at the top of this stack
	 * @throws EmptyStackException if this stack is empty
	 */
	public int pop() throws EmptyStackException 
	{
		int topNumber;
		if (empty())
		{
			topNumber = buffer[size];
			size--;
		}
		else 
		{
			throw new EmptyStackException();
		}
		
		return topNumber;
	}
	
	/**
	 * Looks at the number at the top of this stack without removing it from the stack. 
	 * 
	 * @return the number at the top of this stack
	 * @throws EmptyStackException if this stack is empty
	 */
	public int peek() throws EmptyStackException
	{
		int topNumber;
		if (empty())
		{
			topNumber = buffer[size];
		}
		else 
		{
			throw new EmptyStackException();
		}
		
		return topNumber;
		
	}

	/**
	 * Tests if this stack is empty. 
	 * 
	 * @return true if and only if this stack contains no items; false otherwise.
	 */
	public boolean empty() 
    {
		if (size == 0)
		{
			return true;
		}
		else
		{
			return false;
		}
	}
	
	/**
	 * Get the size of this stack.
	 * 
	 * @return the current number of items on this stack
	 */
	public int size() 
    {
		return size;
	}
	
	/**
	 * Get the capacity of this stack.
	 *    
	 * @return the maximum number of items this stack can hold without having to grow
	 */
	public int capacity() 
    {
		return buffer.length;
	}
}
```


----------



## SlaterB (27. Mrz 2012)

und der Test ist eine Blackbox, du hast keinen Code, auch keine Fehlermeldung/ Log, die irgendwas an Informationen bietet?

nur den Code zu posten + 'irgendwas ist bestimmt falsch, falls es nicht nur an meiner Bedienung des Tests usw. liegt' ist bisschen knapp,

eine gute Übung wäre auch, selber bisschen zu testen versuchen, schreibe dir eine main-Methode, füge 5 Elemente ein, 
entferne 3, schaue ob noch die richtigen 2 drin sind und ähnliches


----------



## kurtisblow (27. Mrz 2012)

Ja, ich habe auch schon versucht zu debuggen, leider kein Erfolg.

Der JUnit4 Test testet folgendes:


```
package u4a1;

import org.junit.Test;
import org.junit.Assert;

/**
 * Tests for the dynamically growing stack.
 */
public class Tests {
	/**
	 * Create a small stack and push one item.
	 */
	@Test public void create()
	{
		Stack stack = new Stack(1);
		Assert.assertEquals("capacity is wrong", 1, stack.capacity());
		Assert.assertEquals("size is wrong", 0, stack.size());
		Assert.assertTrue(stack.empty());
		
		stack.push(23);
		Assert.assertEquals("capacity is wrong", 1, stack.capacity());
		Assert.assertEquals("size is wrong", 1, stack.size());
		Assert.assertFalse(stack.empty());
	}

	/**
	 * Check toString for empty stack.
	 */
	@Test public void toStringEmpty()
	{
		Stack stack = new Stack(3);
		Assert.assertEquals("string representation is wrong", "[]", stack.toString());
	}

	/**
	 * Check toString for filled stack.
	 */
	@Test public void toStringGeneric()
	{
		Stack stack = new Stack(3);
		stack.push(1);
		stack.push(2);
		Assert.assertEquals("string representation is wrong", "[1, 2]", stack.toString());
	}
	
	/**
	 * Check that pop throws an EmptyStackException
	 */
	@Test(expected = java.util.EmptyStackException.class)
	public void popFail()
	{
		new Stack(1).pop();
	}

	/**
	 * Check that peek throws an EmptyStackException
	 */
	@Test(expected = java.util.EmptyStackException.class)
	public void peekFail()
	{
		new Stack(1).peek();
	}
	
	/**
	 * Check behavior of push, peek and pop without reaching the initial capacity.
	 */
	@Test public void pushPeekAndPop()
	{
		final int max = 5;
		Stack stack = new Stack(max);
		Assert.assertEquals("capacity is wrong", max, stack.capacity());
		Assert.assertEquals("size is wrong", 0, stack.size());
		Assert.assertTrue(stack.empty());
		
		for (int i=0; i<max; i++) {
			stack.push(i);
			Assert.assertEquals("capacity is wrong", max, stack.capacity());
			Assert.assertEquals("size is wrong", i+1, stack.size());
		}

		Assert.assertFalse(stack.empty());
		
		for (int i=max-1; i>=0; i--) {
			Assert.assertEquals("top string is wrong", i, stack.peek());
			Assert.assertEquals("capacity is wrong", max, stack.capacity());
			Assert.assertEquals("size is wrong", i+1, stack.size());

			Assert.assertEquals("top string is wrong after first peek", i, stack.peek());
			Assert.assertEquals("capacity is wrong", max, stack.capacity());
			Assert.assertEquals("size is wrong", i+1, stack.size());

			Assert.assertEquals("popped string is wrong", i, stack.pop());
			Assert.assertEquals("capacity is wrong", max, stack.capacity());
			Assert.assertEquals("size is wrong", i, stack.size());
		}
		
		Assert.assertTrue(stack.empty());
	}
	
	/**
	 * Check behavior of push, peek and pop when forcing the stack to grow once.
	 */
	@Test public void grow()
	{
		final int max = 5;
		Stack stack = new Stack(max);
		Assert.assertEquals("capacity is wrong", max, stack.capacity());
		Assert.assertEquals("size is wrong", 0, stack.size());
		Assert.assertTrue(stack.empty());
		
		for (int i=0; i<max; i++) {
			stack.push(i);
			Assert.assertEquals("capacity is wrong", max, stack.capacity());
			Assert.assertEquals("size is wrong", i+1, stack.size());
		}

		Assert.assertFalse(stack.empty());
		
		stack.push(max);
		Assert.assertEquals("capacity is wrong", 2*max, stack.capacity());
		Assert.assertEquals("size is wrong", max+1, stack.size());
		
		
		for (int i=max; i>=0; i--) {
			Assert.assertEquals("top number is wrong", i, stack.peek());
			Assert.assertEquals("capacity is wrong", 2*max, stack.capacity());
			Assert.assertEquals("size is wrong", i+1, stack.size());

			Assert.assertEquals("top number is wrong after first peek", i, stack.peek());
			Assert.assertEquals("capacity is wrong", 2*max, stack.capacity());
			Assert.assertEquals("size is wrong", i+1, stack.size());

			Assert.assertEquals("popped number is wrong", i, stack.pop());
			Assert.assertEquals("capacity is wrong", 2*max, stack.capacity());
			Assert.assertEquals("size is wrong", i, stack.size());
		}
		
		Assert.assertTrue(stack.empty());		
	}
}
```


----------



## tfa (27. Mrz 2012)

Aber die Meldungen, die der Test ausgespuckt hat, hast du dir schon angesehen? Das sieht doch recht ausführlich aus. Die Asserts haben sogar Kommentare.


----------



## kurtisblow (27. Mrz 2012)

Ok, ich glaube ich habe es gleich,
wie ist es aber möglich ein element eines Arrays zu löschen?
array.remove(x) geht nicht, auch wenn ich import java.util.ArrayList; importiere.


----------



## SlaterB (27. Mrz 2012)

wenn man vor so einem JUnit-Test nur ehrfürchtig erstaunt, dann ist er in diesem Fall eher kontraproduktiv,
verdeckt zudem vielleicht noch die auftretenden Exceptions, oder die sich einfach zum Posten eingespart, genau wie ein eventuelles Log


```
Stack stack = new Stack(1);
        stack.push(23);
```
führt direkt in eine Exception, warum kann man doch in der Methode push wunderbar verfolgen,
was sind die Ausgangswerte, was soll passieren, was passiert tatsächlich,

keine Ideen?


edit:
> wie ist es aber möglich ein element eines Arrays zu löschen?

du kannst Werte von Array-Positionen ändern oder neue kleinere Arrays erstellen


----------



## Landei (27. Mrz 2012)

Nebenbei gefragt: *Musst* du den Stack mit einem Array implementieren? Mit einer verketteten Liste würde es wesentlich (!) leichter, selbst wenn du die selbst schreibst.


----------



## kurtisblow (27. Mrz 2012)

es muss leider in einem array sein, so vorgegeben


----------



## Landei (27. Mrz 2012)

Ach immer diese Leerkräfte! Die drehen sicher auch Schrauben mit der Kneifzange rein und hebeln Nägel mit dem Schraubendreher raus...


----------



## SlaterB (27. Mrz 2012)

wie man sieht bereitet es ernsthafte Probleme, mit Array, Indexen, Größe umzugehen,
die Aufgabe passt also ideal, großes Lob an die Lehrkräfte


----------



## Landei (28. Mrz 2012)

Es gibt andere Aufgaben, wo das auch so ist, aber Arrays der "richtige" Typ für den Job sind, etwa In-Place-Varianten von Sortierverfahren. Neulinge sollten von Anfang an lernen einzuschätzen, ob sich Komplexität vermeiden lässt (wie bei Stack) oder nicht (wie bei den Sortierverfahren). Prinzipiell empfinde ich eine Vorgabe "ihr nehmt jetzt das und das, um diese Aufgabe zu lösen" aus pädagogischer Sicht als Schlag ins Wasser, weil so von vornherein jede Kreativität unterbunden wird (natürlich muss man die Verwendung von Bibliotheksklassen einschränken, Selbermachen muss schon sein)


----------

