package net.datastructures;
/**
* Implementation of the Stack interface using a fixed-length array.
* An exception is thrown if a push operation is attempted when the
* size of the stack is equal to the length of the array.
*
* @author Natasha Gelfand
* @author Roberto Tamassia
* @see FullStackException
*/
public class ArrayStack implements Stack {
/**
* Default length of the array used to implement the stack.
*/
public static final int CAPACITY = 1000;
/**
* Length of the array used to implement the stack.
*/
protected int capacity;
/**
* Array used to implement the stack.
*/
protected Object S[];
/**
* Index of the top element of the stack in the array.
*/
protected int top = -1;
/**
* Initialize the stack to use an array of default length CAPACITY.
*/
public ArrayStack() {
// this(CAPACITY);
this(10);
}
/**
* Initialize the stack to use an array of given length.
*
* @param cap length of the array.
*/
public ArrayStack(int cap) {
capacity = cap;
S = new Object[capacity];
}
/**
* O(1) time.
*/
public int size() {
return (top + 1);
}
/**
* O(1) time.
*/
public boolean isEmpty() {
return (top < 0);
}
/**
* O(1) time.
* @exception FullStackException if the array is full.
*/
public void push(Object obj) throws FullStackException {
if (size() == capacity)
throw new FullStackException("Stack overflow.");
S[++top] = obj;
}
/**
* O(1) time.
*/
public Object top() throws EmptyStackException {
if (isEmpty())
throw new EmptyStackException("Stack is empty.");
return S[top];
}
/**
* O(1) time.
*/
public Object pop() throws EmptyStackException {
Object elem;
if (isEmpty())
throw new EmptyStackException("Stack is Empty.");
elem = S[top];
S[top--] = null; // dereference S[top] for garbage collection.
return elem;
}
}
|