Skip to main content
Lesson 38 - Stacks
ZIPPDF (letter)
Lesson MenuPreviousNext
  
Implementation Strategies for a Stack Type page 4 of 6

  1. A Stack interface is defined to formalize the stack methods. See Handout H.A.38.1, Stack Interface for the details.

    public interface Stack
    {
      boolean isEmpty();
      void push(Object obj);
      Object pop();
      Object peekTop();
    }
  2. The Stack interface above specifies the push and pop methods, the boolean method isEmpty, and an additional method peekTop that returns the value of the top element without removing it from the stack.

  3. The following listing shows the Stack interface implemented in the ArrayStack class:

    public class ArrayStack implements Stack 
    {
      private java.util.ArrayList array;
    
      public ArrayStack()
      { array = new java.util.ArrayList(); }
      public boolean isEmpty() { return array.size() == 0; }
      public void push(Object obj) { array.add(obj); }
      public Object pop() { return array.remove(array.size() - 1); }
      public Object peekTop() { return array.get(array.size() - 1); }
    }
  4. The data structure used in the ArrayStack class is an ArrayList. This allows for resizing of the stack as needed to make it larger.

  5. Here is a short program illustrating usage of the ArrayStack class.

    // Example program using the ArrayStack class
    
    public static void main(String[] args)
    {
      ArrayStack stack = new ArrayStack();
        
      for (int k = 1; k <= 5; k++)
        stack.push(new Integer(k));
    
      while (!(stack.isEmpty()))
      {
        System.out.print(stack.pop() + "  ");
      }
    }
  6. Another approach would be to use a linked list that would support true dynamic resizing. As you push data onto the stack another node is added to the appropriate end of the linked list. When data is popped from the stack, the linked list would be reduced in size. The following listing shows the Stack interface implemented in the ListStack class as a java.util.LinkedList:

    public class ListStack implements Stack
    {
      private java.util.LinkedList list;
    
      public ListStack() { list = new java.util.LinkedList(); }
      public boolean isEmpty() { return list.isEmpty(); }
      public void push(Object obj) { list.addFirst(obj); }
      public Object pop() { return list.removeFirst(); }
      public Object peekTop() { return list.getFirst(); }
    }


Lesson MenuPreviousNext
Contact
 ©ICT 2003, All Rights Reserved.