Assignment 5 - The stack data structure

Due Before class on Nov 14th

The objective of this assignment is to learn the concept of the "Abstract Data Type" or ADT by writing an implementation of an ADT called a stack. A stack is very similar to a queue. They have the same interface, although there is one key difference in the way they behave. A queue is FIFO (first in first out) while a stack is LIFO (last in first out. An example is a stack of plates in a cafeteria line. The last plate put on top of the stack will be the first one taken off. So the first plate added to the stack is at the bottom and will be the last plate taken off.

A stack is a handy way to reverse the order of a set of objects. Below is a simple application called "ReverseArgs" which reads a the command line arguments and prints them in reverse order. The assignment is to write a Stack class to use with this application. As always email me what you have by the due data—working or not.

The Stack class used by the ReverseArgs application has the following interface:

public void push(Object o)
Adds a new object onto the stack.
public Object pop()
Removes an Object from the stack and returns that object.
public boolean notEmpty()
returns true if there is at least one object on the stack. returns false if the stack is empty.

Note that the constructor for Stack used in ReverseArgs takes no arguments. If you write an array-based implementation like I did in the Queue example, you will need to choose some reasonable default value for the length of the array you use, or write code that creates a new bigger array when too many push() calls cause the stack to overflow.

ReverseArgs.java

class ReverseArgs {


    static public void main(String[] arg) {
	Stack stack = new Stack();

	//push all of the args onto a stack
	for (int i=0; i<arg.length; i++) {
	    stack.push(arg[i]);
	}

	//pop them all off in reverse order
	while (stack.notEmpty()) {
	    System.out.print( stack.pop() + " " );
	}
	System.out.println();
    }
}

Helpful Links