Writing a Stack class

Problem with peek/pop methods

Page 1 of 1

13 Replies - 25801 Views - Last Post: 04 April 2009 - 04:43 PM Rate Topic: -----

#1 xxwolfsrainxx   User is offline

  • D.I.C Head

Reputation: 1
  • View blog
  • Posts: 93
  • Joined: 04-December 08

Writing a Stack class

Posted 04 April 2009 - 11:52 AM

I'm having a problem with my peek and pop methods.
In my stack tester for my stack it states, java.lang.IndexOutOfBoundException.
Stack class
//Implements a Stack, which is a data structure that works like a "line".
//A Stack is a LIFO (last-in-first-out)

import java.util.*;

public class Stack<E>   //the user can define what type when they create it
{
	//data - just used the ArrayList. It will hold each element
	private ArrayList<E> data;

	//constructor
	public Stack()
	{
		data = new ArrayList<E>();	 //the constructor will actually create the aggregate class instance
	}

	//methods

	//push - inserts the obj into the stack
	public E push(E obj)
	{
		data.add(obj);
		return obj;
	}


	//pop - pops the last item off the stack
	public E pop()
	{
		if (data.size() == 0)
		{
			throw new EmptyStackException();
		}
		else
		{
			return data.remove(data.size());   //the ArrayList method will remove and return it,
		}
	}

	//peek - looks at the last thing in the stack without removing it
	public E peek()
	{
		if (data.isEmpty())
			throw new EmptyStackException();
		else
		return data.get(data.size());

	}

	//empty -tests if the stack is empty
	public Boolean empty()
	{
		if(data.size() == 0)
			return true;
		else
			return false;
	}

	//search - searchs the stack for the item requested by the user
	public int search(Object o)
	{
		if(data.size() == 0)
			return -1;
		else if(data.contains(o))
		{
			//Tricky spot. Had to add one to the indexOf
			//This fixed the problem of searching for something.
			return data.indexOf(o)+1;
		}
		else
			return -1;

	}

	//toString - toString for the stack
	public String toString()
	{
		return data.toString();
	}

} 

Stack Tester
[code]

public class StackTester
{
public static void main(String[ ] args)
{
//declare an instance of your Stack and one for java built-in Stack (will recreate for each test)
Stack<Integer> stk;
java.util.Stack<Integer> javastk;

System.out.println("This program will test your Stack implementation against the");
System.out.println("results returned by Java's built-in Stack class.");
System.out.println("------------------------------------------------------------");

System.out.println("\nTesting with an empty stack");

System.out.println("\n----- Testing pop()");

stk = new Stack<Integer>();
javastk = new java.util.Stack<Integer>();
try
{
int intresult;
boolean boolresult;
intresult = stk.pop();
System.out.println("your result: " + intresult + "\tyour contents: " + stk);
}
catch (Throwable ex)
{
System.out.println("your result: " + ex + "\tyour contents: " + stk);
}
try
{
int intresult;
boolean boolresult;
intresult = javastk.pop();
System.out.println("Java result: " + intresult + "\tJava contents: " + stk);
}
catch (Throwable ex)
{
System.out.println("Java result: " + ex + "\tJava contents: " + stk);
}

System.out.println("\n----- Testing peek()");

stk = new Stack<Integer>();
javastk = new java.util.Stack<Integer>();
try
{
int intresult;
boolean boolresult;
intresult = stk.peek();
System.out.println("your result: " + intresult + "\tyour contents: " + stk);
}
catch (Throwable ex)
{
System.out.println("your result: " + ex + "\tyour contents: " + stk);
}
try
{
int intresult;
boolean boolresult;
intresult = javastk.peek();
System.out.println("Java result: " + intresult + "\tJava contents: " + stk);
}
catch (Throwable ex)
{
System.out.println("Java result: " + ex + "\tJava contents: " + stk);
}

System.out.println("\n----- Testing empty()");

stk = new Stack<Integer>();
javastk = new java.util.Stack<Integer>();
try
{
int intresult;
boolean boolresult;
boolresult = stk.empty();
System.out.println("your result: " + boolresult + "\tyour contents: " + stk);
}
catch (Throwable ex)
{
System.out.println("your result: " + ex + "\tyour contents: " + stk);
}
try
{
int intresult;
boolean boolresult;
boolresult = javastk.empty();
System.out.println("Java result: " + boolresult + "\tJava contents: " + stk);
}
catch (Throwable ex)
{
System.out.println("Java result: " + ex + "\tJava contents: " + stk);
}

System.out.println("\n----- Testing push(4)");

stk = new Stack<Integer>();
javastk = new java.util.Stack<Integer>();
try
{
int intresult;
boolean boolresult;
intresult = stk.push(4);
System.out.println("your result: " + intresult + "\tyour contents: " + stk);
}
catch (Throwable ex)
{
System.out.println("your result: " + ex + "\tyour contents: " + stk);
}
try
{
int intresult;
boolean boolresult;
intresult = javastk.push(4);
System.out.println("Java result: " + intresult + "\tJava contents: " + stk);
}
catch (Throwable ex)
{
System.out.println("Java result: " + ex + "\tJava contents: " + stk);
}

System.out.println("\n----- Testing search(2)");

stk = new Stack<Integer>();
javastk = new java.util.Stack<Integer>();
try
{
int intresult;
boolean boolresult;
intresult = stk.search(2);
System.out.println("your result: " + intresult + "\tyour contents: " + stk);
}
catch (Throwable ex)
{
System.out.println("your result: " + ex + "\tyour contents: " + stk);
}
try
{
int intresult;
boolean boolresult;
intresult = javastk.search(2);
System.out.println("Java result: " + intresult + "\tJava contents: " + stk);
}
catch (Throwable ex)
{
System.out.println("Java result: " + ex + "\tJava contents: " + stk);
}

//************************************************
System.out.println("\n\nTesting with a Stack with a single element (99)");

System.out.println("\n----- Testing pop()");

stk = new Stack<Integer>();
stk.push(99);
javastk = new java.util.Stack<Integer>();
javastk.push(99);
try
{
int intresult;
boolean boolresult;
intresult = stk.pop();
System.out.println("your result: " + intresult + "\tyour contents: " + stk);
}
catch (Throwable ex)
{
System.out.println("your result: " + ex + "\tyour contents: " + stk);
}
try
{
int intresult;
boolean boolresult;
intresult = javastk.pop();
System.out.println("Java result: " + intresult + "\tJava contents: " + stk);
}
catch (Throwable ex)
{
System.out.println("Java result: " + ex + "\tJava contents: " + stk);
}

System.out.println("\n----- Testing peek()");

stk = new Stack<Integer>();
stk.push(99);
javastk = new java.util.Stack<Integer>();
javastk.push(99);
try
{
int intresult;
boolean boolresult;
intresult = stk.peek();
System.out.println("your result: " + intresult + "\tyour contents: " + stk);
}
catch (Throwable ex)
{
System.out.println("your result: " + ex + "\tyour contents: " + stk);
}
try
{
int intresult;
boolean boolresult;
intresult = javastk.peek();
System.out.println("Java result: " + intresult + "\tJava contents: " + stk);
}
catch (Throwable ex)
{
System.out.println("Java result: " + ex + "\tJava contents: " + stk);
}

System.out.println("\n----- Testing empty()");

stk = new Stack<Integer>();
stk.push(99);
javastk = new java.util.Stack<Integer>();
javastk.push(99);
try
{
int intresult;
boolean boolresult;
boolresult = stk.empty();
System.out.println("your result: " + boolresult + "\tyour contents: " + stk);
}
catch (Throwable ex)
{
System.out.println("your result: " + ex + "\tyour contents: " + stk);
}
try
{
int intresult;
boolean boolresult;
boolresult = javastk.empty();
System.out.println("Java result: " + boolresult + "\tJava contents: " + stk);
}
catch (Throwable ex)
{
System.out.println("Java result: " + ex + "\tJava contents: " + stk);
}

System.out.println("\n----- Testing push(4)");

stk = new Stack<Integer>();
stk.push(99);
javastk = new java.util.Stack<Integer>();
javastk.push(99);
try
{
int intresult;
boolean boolresult;
intresult = stk.push(4);
System.out.println("your result: " + intresult + "\tyour contents: " + stk);
}
catch (Throwable ex)
{
System.out.println("your result: " + ex + "\tyour contents: " + stk);
}
try
{
int intresult;
boolean boolresult;
intresult = javastk.push(4);
System.out.println("Java result: " + intresult + "\tJava contents: " + stk);
}
catch (Throwable ex)
{
System.out.println("Java result: " + ex + "\tJava contents: " + stk);
}

System.out.println("\n----- Testing search(2)");

stk = new Stack<Integer>();
stk.push(99);
javastk = new java.util.Stack<Integer>();
javastk.push(99);
try
{
int intresult;
boolean boolresult;
intresult = stk.search(2);
System.out.println("your result: " + intresult + "\tyour contents: " + stk);
}
catch (Throwable ex)
{
System.out.println("your result: " + ex + "\tyour contents: " + stk);
}
try
{
int intresult;
boolean boolresult;
intresult = javastk.search(2);
System.out.println("Java result: " + intresult + "\tJava contents: " + stk);
}
catch (Throwable ex)
{
System.out.println("Java result: " + ex + "\tJava contents: " + stk);
}

System.out.println("\n----- Testing search(99)");

stk = new Stack<Integer>();
stk.push(99);
javastk = new java.util.Stack<Integer>();
javastk.push(99);
try
{
int intresult;
boolean boolresult;
intresult = stk.search(99);
System.out.println("your result: " + intresult + "\tyour contents: " + stk);
}
catch (Throwable ex)
{
System.out.println("your result: " + ex + "\tyour contents: " + stk);
}
try
{
int intresult;
boolean boolresult;
intresult = javastk.search(99);
System.out.println("Java result: " + intresult + "\tJava contents: " + stk);
}
catch (Throwable ex)
{
System.out.println("Java result: " + ex + "\tJava contents: " + stk);
}

System.out.println("\n----- Testing search(\"astring\")");

stk = new Stack<Integer>();
stk.push(99);
javastk = new java.util.Stack<Integer>();
javastk.push(99);
try
{
int intresult;
boolean boolresult;
intresult = stk.search("astring");
System.out.println("your result: " + intresult + "\tyour contents: " + stk);
}
catch (Throwable ex)
{
System.out.println("your result: " + ex + "\tyour contents: " + stk);
}
try
{
int intresult;
boolean boolresult;
intresult = javastk.search("astring");
System.out.println("Java result: " + intresult + "\tJava contents: " + stk);
}
catch (Throwable ex)
{
System.out.println("Java result: " + ex + "\tJava contents: " + stk);
}


//************************************************
System.out.println("\n\nTesting with a Stack with a many elements (pushed 11, then 12, then 13)");

System.out.println("\n----- Testing pop()");

stk = new Stack<Integer>();
stk.push(11);
stk.push(12);
stk.push(13);
javastk = new java.util.Stack<Integer>();
javastk.push(11);
javastk.push(12);
javastk.push(13);
try
{
int intresult;
boolean boolresult;
intresult = stk.pop();
System.out.println("your result: " + intresult + "\tyour contents: " + stk);
}
catch (Throwable ex)
{
System.out.println("your result: " + ex + "\tyour contents: " + stk);
}
try
{
int intresult;
boolean boolresult;
intresult = javastk.pop();
System.out.println("Java result: " + intresult + "\tJava contents: " + stk);
}
catch (Throwable ex)
{
System.out.println("Java result: " + ex + "\tJava contents: " + stk);
}

System.out.println("\n----- Testing peek()");

stk = new Stack<Integer>();
stk.push(11);
stk.push(12);
stk.push(13);
javastk = new java.util.Stack<Integer>();
javastk.push(11);
javastk.push(12);
javastk.push(13);
try
{
int intresult;
boolean boolresult;
intresult = stk.peek();
System.out.println("your result: " + intresult + "\tyour contents: " + stk);
}
catch (Throwable ex)
{
System.out.println("your result: " + ex + "\tyour contents: " + stk);
}
try
{
int intresult;
boolean boolresult;
intresult = javastk.peek();
System.out.println("Java result: " + intresult + "\tJava contents: " + stk);
}
catch (Throwable ex)
{
System.out.println("Java result: " + ex + "\tJava contents: " + stk);
}

System.out.println("\n----- Testing empty()");

stk = new Stack<Integer>();
stk.push(11);
stk.push(12);
stk.push(13);
javastk = new java.util.Stack<Integer>();
javastk.push(11);
javastk.push(12);
javastk.push(13);
try
{
int intresult;
boolean boolresult;
boolresult = stk.empty();
System.out.println("your result: " + boolresult + "\tyour contents: " + stk);
}
catch (Throwable ex)
{
System.out.println("your result: " + ex + "\tyour contents: " + stk);
}
try
{
int intresult;
boolean boolresult;
boolresult = javastk.empty();
System.out.println("Java result: " + boolresult + "\tJava contents: " + stk);
}
catch (Throwable ex)
{
System.out.println("Java result: " + ex + "\tJava contents: " + stk);
}

System.out.println("\n----- Testing push(4)");

stk = new Stack<Integer>();
stk.push(11);
stk.push(12);
stk.push(13);
javastk = new java.util.Stack<Integer>();
javastk.push(11);
javastk.push(12);
javastk.push(13);
try
{
int intresult;
boolean boolresult;
intresult = stk.push(4);
System.out.println("your result: " + intresult + "\tyour contents: " + stk);
}
catch (Throwable ex)
{
System.out.println("your result: " + ex + "\tyour contents: " + stk);
}
try
{
int intresult;
boolean boolresult;
intresult = javastk.push(4);
System.out.println("Java result: " + intresult + "\tJava contents: " + stk);
}
catch (Throwable ex)
{
System.out.println("Java result: " + ex + "\tJava contents: " + stk);
}

System.out.println("\n----- Testing search(12)");

stk = new Stack<Integer>();
stk.push(11);
stk.push(12);
stk.push(13);
javastk = new java.util.Stack<Integer>();
javastk.push(11);
javastk.push(12);
javastk.push(13);
try
{
int intresult;
boolean boolresult;
intresult = stk.search(12);
System.out.println(stk);
 &nbs

Is This A Good Question/Topic? 0
  • +

Replies To: Writing a Stack class

#2 xxwolfsrainxx   User is offline

  • D.I.C Head

Reputation: 1
  • View blog
  • Posts: 93
  • Joined: 04-December 08

Re: Writing a Stack class

Posted 04 April 2009 - 11:53 AM

The error is happening when I'm testing the peek and pop methods in the tester. Sorry for the double post. Was editing the original and somehow it posted again?

This post has been edited by xxwolfsrainxx: 04 April 2009 - 11:55 AM

Was This Post Helpful? 0
  • +
  • -

#3 mostyfriedman   User is offline

  • The Algorithmi
  • member icon

Reputation: 729
  • View blog
  • Posts: 4,473
  • Joined: 24-October 08

Re: Writing a Stack class

Posted 04 April 2009 - 11:55 AM

i think you should have done it using an array instead of an ArrayList since Stacks have fixed size
Was This Post Helpful? 0
  • +
  • -

#4 xxwolfsrainxx   User is offline

  • D.I.C Head

Reputation: 1
  • View blog
  • Posts: 93
  • Joined: 04-December 08

Re: Writing a Stack class

Posted 04 April 2009 - 11:57 AM

View Postmostyfriedman, on 4 Apr, 2009 - 10:55 AM, said:

i think you should have done it using an array instead of an ArrayList since Stacks have fixed size

Our teacher wants us to implement a stack using an ArrayList. I'd gladly would of used an array instead because they are easier.
Was This Post Helpful? 0
  • +
  • -

#5 mostyfriedman   User is offline

  • The Algorithmi
  • member icon

Reputation: 729
  • View blog
  • Posts: 4,473
  • Joined: 24-October 08

Re: Writing a Stack class

Posted 04 April 2009 - 12:04 PM

 public E pop()
	{
		if (data.size() == 0)
		{
			throw new EmptyStackException();
		}
		else
		{
			return data.remove(data.size()-1);   //the ArrayList method will remove and return it,
		}
	}



public E peek()
	{
		if (data.isEmpty())
			throw new EmptyStackException();
		else
		return data.get(data.size()-1);

	}


this should do it

This post has been edited by mostyfriedman: 04 April 2009 - 12:05 PM

Was This Post Helpful? 1
  • +
  • -

#6 xxwolfsrainxx   User is offline

  • D.I.C Head

Reputation: 1
  • View blog
  • Posts: 93
  • Joined: 04-December 08

Re: Writing a Stack class

Posted 04 April 2009 - 12:08 PM

View Postmostyfriedman, on 4 Apr, 2009 - 11:04 AM, said:

 public E pop()
	{
		if (data.size() == 0)
		{
			throw new EmptyStackException();
		}
		else
		{
			return data.remove(data.size()-1);   //the ArrayList method will remove and return it,
		}
	}



public E peek()
	{
		if (data.isEmpty())
			throw new EmptyStackException();
		else
		return data.get(data.size()-1);

	}


this should do it

Thanks. Could you possibly, if you aren't to busy, explain why you must add the -1?
Was This Post Helpful? 0
  • +
  • -

#7 mostyfriedman   User is offline

  • The Algorithmi
  • member icon

Reputation: 729
  • View blog
  • Posts: 4,473
  • Joined: 24-October 08

Re: Writing a Stack class

Posted 04 April 2009 - 12:11 PM

because like arrays, the first element is at index 0 and the last element is at index n-1
Was This Post Helpful? 1
  • +
  • -

#8 xxwolfsrainxx   User is offline

  • D.I.C Head

Reputation: 1
  • View blog
  • Posts: 93
  • Joined: 04-December 08

Re: Writing a Stack class

Posted 04 April 2009 - 12:12 PM

View Postmostyfriedman, on 4 Apr, 2009 - 11:11 AM, said:

because like arrays, the first element is at index 0 and the last element is at index n-1

Thank you.
Was This Post Helpful? 0
  • +
  • -

#9 mostyfriedman   User is offline

  • The Algorithmi
  • member icon

Reputation: 729
  • View blog
  • Posts: 4,473
  • Joined: 24-October 08

Re: Writing a Stack class

Posted 04 April 2009 - 12:13 PM

you are most welcome ;)
Was This Post Helpful? 0
  • +
  • -

#10 cfoley   User is offline

  • Cabbage
  • member icon

Reputation: 2391
  • View blog
  • Posts: 5,015
  • Joined: 11-December 07

Re: Writing a Stack class

Posted 04 April 2009 - 12:36 PM

Oh, I didn't see this thread when I replied to the otehr one.

Why do you say stacks are of fixed size? I thought one of their properties is that they grow and shrink as they are used. Assuming you only need push and pop, an implementation analogous to a linked list seems perfectly space efficient while one based on Vector or ArrayList seems better for time efficiency.
Was This Post Helpful? 0
  • +
  • -

#11 mostyfriedman   User is offline

  • The Algorithmi
  • member icon

Reputation: 729
  • View blog
  • Posts: 4,473
  • Joined: 24-October 08

Re: Writing a Stack class

Posted 04 April 2009 - 12:48 PM

nope LinkedLists and Trees dont have a specific size, however stacks and queues do have a specific size that's why they need isFull() and isEmpty() methods
Was This Post Helpful? 0
  • +
  • -

#12 cfoley   User is offline

  • Cabbage
  • member icon

Reputation: 2391
  • View blog
  • Posts: 5,015
  • Joined: 11-December 07

Re: Writing a Stack class

Posted 04 April 2009 - 01:41 PM

Is there a different name for a LIFO structure that can grow and shrink then? It seems a useful property for a data structure with that behavior.

Edit: I've just had a quick look around. The Java implementation of Stack uses a Vector and doesn't define the isFull() method. Wikipedia (not the best source, I know) says this:

Quote

Due to practical memory limits, stacks are often of a particular size, ...

A stack's data structure can be implemented by other data structures such as arrays, linked lists and trees.

This post has been edited by cfoley: 04 April 2009 - 01:54 PM

Was This Post Helpful? 0
  • +
  • -

#13 baavgai   User is offline

  • Dreaming Coder
  • member icon


Reputation: 7205
  • View blog
  • Posts: 15,018
  • Joined: 16-October 07

Re: Writing a Stack class

Posted 04 April 2009 - 03:48 PM

Capacity is not a requirement for stack. Technically, the only thing needed is push and pop. For extra credit, peek is nice and isEmpty or hasValues. In addition to using an array for implementation, a stack lends itself really well to a linked list. The primary reason for implementing a linked list is dynamic sizing.

Honestly, this should really be enough to call yourself a stack:
interface IStack<T extends Object> {
	void push(T item);
	T pop();
	T peek();
	boolean isEmpty();
}



I chose "extends Object" in the interface, because I want to be able to work with nulls.
Was This Post Helpful? 1
  • +
  • -

#14 cfoley   User is offline

  • Cabbage
  • member icon

Reputation: 2391
  • View blog
  • Posts: 5,015
  • Joined: 11-December 07

Re: Writing a Stack class

Posted 04 April 2009 - 04:43 PM

Thanks for clearing that up. :)
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1