MyStack.java

gistfile1.txt

import java.util.*;

/**
 * Array-based stack implementation.
 * 
 * Kyle Kingsbury CS127 (Carleton College, Winter 2006)
 */
public class MyStack<E> implements RealStack<E> {

	// Data

	E[] stack; // Stack data
	int size; // Number of stack elements
	int INITIAL_CAPACITY = 16; // Default size of the array

	// Constructors

	/**
	 * Creates a stack of the default initial capacity.
	 */
	public MyStack() {
		// Cast from object because of generic array idiosyncracies.
		// See "Objects, Abstraction, Data Structures, and Design using
		// Java", by Koffman and Wolfgang, page 274
		stack = (E[]) new Object[INITIAL_CAPACITY];
		size = 0;
	}

	/**
	 * Creates a stack of the given size.
	 */
	public MyStack(int capacity) {
		stack = (E[]) new Object[capacity];
		INITIAL_CAPACITY = capacity;
		size = 0;
	}

	// Public methods

	/**
	 * Pushes an item onto the stack
	 */
	public void push(E item) {
		resizeArrayIfNecessary();
		stack[size] = item;
		size++;
	}

	/**
	 * Returns the item on the top of the stack. Stack remains unchanged. An
	 * EmptyStackException is thrown if the stack is empty.
	 */
	public E peek() throws EmptyStackException {
		if (empty()) {
			throw new EmptyStackException();
		}
		return stack[size - 1];
	}

	/**
	 * Removes and returns the item on the top of the stack. An
	 * EmptyStackException is thrown if the stack is empty.
	 */
	public E pop() throws EmptyStackException {
		if (empty()) {
			throw new EmptyStackException();
		}
		E item = stack[size - 1];
		stack[size - 1] = null;
		size--;
		resizeArrayIfNecessary();
		return item;
	}

	/**
	 * Returns true if there are no elements left in the stack.
	 */
	public boolean empty() {
		if (size <= 0) {
			return true;
		} else {
			return false;
		}
	}

	/**
	 * Returns string representation of stack.
	 */
	public String toString() {
		String str = "";
		for (int i = 0; i < stack.length; i++) {
			if (stack[i] == null) {
				break;
			}
			str = str + "[" + stack[i] + "],";
		}
		return str;
	}

	// Private helper methods

	/**
	 * Expands and compacts array as necessary. When the stack is filled to
	 * capacity, the array used to store it is doubled in size. When the stack
	 * is less than 1/4th filled, the size of the stack is halved. The stack
	 * will never be smaller than it's initial capacity.
	 */
	private void resizeArrayIfNecessary() {
		if (size > INITIAL_CAPACITY / 4 && size < stack.length / 4) {
			// Array is only 1/4th used. Compact the stack to 1/2
			// its current size.
			E[] tempArray = (E[]) new Object[stack.length / 2];
			System.arraycopy(stack, 0, tempArray, 0, size);
			stack = tempArray;
		} else if (size >= stack.length) {
			// Array is full. Double the size of the stack.
			E[] tempArray = (E[]) new Object[stack.length * 2];
			System.arraycopy(stack, 0, tempArray, 0, size);
			stack = tempArray;
		} else {
			return;
		}
	}
}