Create your own Stack Class, call it ArrayIntStack.java and write the standard four public Stack methods as listed below (this is the easy part of the assignment). All methods in your ArrayIntStack must have O(constant) run-time. Your ArrayIntStack extends no other Classes from the Java API. You must provide a default constructor.

1. boolean empty(); Tests if this stack is empty (watch spelling here, as I will) 2. int peek(); Looks at the object at the top of this stack without removing it from the stack. 3. int pop(); Removes the object at the top of this stack and returns that object as the value of this function. 4. int push(int item); Pushes an item onto the top of this stack, return what was pushed.

Additional methods, code, etc... will also need to be provided, so the client can use an iterator:

5. public class IntStackIterator { // similar to what the BJP authors show, but without a remove() implemented 6. public IntStackIterator iterator() method so the client can browse through the data with .next() etc... Start the iterator at the top of the stack!!!

Suggestion: Look at ArrayIntList.java as a reference to start his Assignment, Notice how ArrayIntList.java is fundamentally the ArrayIntList4 from the Chapter 15 downloads, plus an internal Iterator as used by Practice-IT, plus many other constructors (...) and operators that you do not need to do for this Assignment. Understand how ArrayIntList.java works, and this Assignment will start to look easy.

Iterate through your array from top (end) to bottom (index 0), so the top of the Stack is returned from the first .next(). This is backwards from the textbook ArrayIntListIterator example, but what I require for your Stack, as then you need to really understand what an iterator is doing, and Stacks are kind of backwards when compared to Lists, the first thing you see is the top. It only makes sense, so push and pop work on the top (end) of the array.

You must throw an "appropriate" Exception (e.g. EmptyStackException) for illegal peek, pop, etc... operations. Regarding size, let's keep out Stack Class as O(constant), beyond the initial constructor size, another push(int) will throw Stack Overflow. Two constructors, a single parameter that specifies initial array size, and no parameter default to a size of 20.

Repeat: Big-O must be O(constant). The client code can have loop and anything, but your Stack Class for this assignment is strictly O(constant), so think carefully about using an Oracle code line Arrays, might not be O(constant)? Know what O(constant) means!!!

ARRAYINTLIST.JAVA CODE:

import java.util.Arrays;

public class ArrayIntList { // implements Iterable { private int[] elementData; // list of integers private int size = 0; // current number of elements in the list public static final int DEFAULT_CAPACITY = 10;

// EXERCISE CODE GOES HERE, to keep it organized, might be on a Quiz some day??? public int lastIndexOf(int value) { // changed to non-static, used as member method now for (int i = elementData.length - 1; i >= 0; i--) { if (elementData[i] == value) { // changed array to elementData return i; } } return -1; }

TEST CODE:

public class Post {

public static void main(String[] args) {

// Constructor overloaded ArrayIntStack bag18 = new ArrayIntStack(); // default array size ArrayIntStack bag99 = new ArrayIntStack(1000); // other size

bag18.push(42); bag18.push(24); bag18.push(-33); // works without the generic Iterator from Oracle ArrayIntStack.IntStackIterator handle = bag18.iterator(); while (handle.hasNext()) { // loop is Big-O O(N) System.out.println(handle.next()); } System.out.println(bag18.empty()); System.out.println(bag18.push(42)); System.out.println(bag18.pop()); System.out.println(bag18.peek()); // required: try { bag99.pop(); } catch (Exception e) { System.out.println("What was thrown: " + e); } // required: try { for (int i=1; i<100; i++) bag18.push(i); } catch (Error e) { System.out.println("What was thrown: " + e); } // optional: // if you implement Oracle Iterable //for (Integer i : bag18) System.out.println(i); }

}