Array Implementation of a Stack

last updated 2/9/07

 


Implementation

By "copy" or by "reference"? That is, does the stack hold a copy of the item or just a reference to the item?

Given the nature of stacks, that only the top element is accessible and there is no abstract expecation that the contents can be changed, then by reference is the better choice.


 


Array Implementation


// This implementation is based on a static array.  If the stack
// becomes full, then no more items can be pushed.
// The user can specify the stack's capacity when it is created.
// This is slightly different from D/J/W


public class ArrayStack implements StackInterface {

   public final static int DEFAULT_CAPACITY = 100;
   private Object stack[];     // The array that holds the stack
   private int top;            // Index of top item on the stack

   // Creates a stack with the default capacity
   public ArrayStack (){
      this(DEFAULT_CAPACITY);
 }

   // Creates a stack with a user-specified capacity
 public ArrayStack (int capacity){
    if (capacity < 1)
       throw new IllegalArgumentException (
                      "Capacity must be > 0");
    stack = new Object[capacity];
    top = -1;
 }
    
 public boolean isEmpty(){
     return top == -1;
 }
    
 public boolean isFull(){
    return size() == stack.length;
 }
    
 public Object top(){
    if (isEmpty())
       throw new StackUnderflowException ("Top attempted on empty stack");
    return stack[top];
 }

 public Object pop(){
    if (isEmpty())
       throw new StackUnderflowException (
                "Pop attempted on empty stack");
    Object topItem = stack[top];
    stack[top] = null; //permit garbage collection
    top--;
    return topItem;
 }

 public void push(Object item){
    if (item == null)
       throw new IllegalArgumentException ("
                             Item is null");
    if (isFull())
       throw new StackOverflowException (
                    "Push attempted on full stack");
    top++; 
    stack[top] = item;
 }    
    
 public int size(){
    return top + 1;
 }
}

 

 


ArrayList Implementation

This implementation takes advantage of the arrayList operations for management of the "top" of the stack.


// This implementation is based on the ArrayList class.  
// This is slightly different from D/J/W


public class ArrayListStack implements StackInterface {

   private ArrayList stack;     // The arrayList holds the stack

   // Creates a stack with the default capacity
   public ArrayListStack (){
      stack = new ArrayList();
   }

   public boolean isEmpty(){
      return stack.size() == 0;
   }
    
   public boolean isFull(){
      return false;
   }
    
   public Object top(){
      if (isEmpty())
         throw new StackUnderflowException (
                "Top attempted on empty stack");
      return stack.get(stack.size()-1);
   }

   public Object pop(){
      if (isEmpty())
         throw new StackUnderflowException (
                "Pop attempted on empty stack");
      Object topItem = stack.get(stack.size()-1);
      stack.remove(stack.size()-1);
      return topItem;
   }

   public void push(Object item){
      if (item == null)
         throw new IllegalArgumentException (
                              "Item is null");
      stack.add(item);
   }    
    
   public int size(){
      return stack.size();
   }
}

 

 

 


Example ArrayStack

StackInterface myStack;
myStack = new ArrayStack(4);
myStack.push(A);
myStack.push(B);
myStack.push(C);
0
A
1
B
2
C
3
^

Realize that A, B, C are really pointers to objects