AP Central: The College Board's Online Home for AP Professionals
Print Page
Here is the article in a print-friendly format. Click the button above to print this page.
AP Computer Science AB: Implementation Classes and Interfaces

Implementation Classes for Linked List and Tree Nodes
The implementation of list and tree structures is a part of the AB Computer Science course, but the Java standard is understandably silent about implementation details. Instructors and textbooks use a number of minor variations for implementing list and tree data structures. To facilitate a uniform style for the formulation of test questions, the AP Computer Science Exam uses the node classes that are listed in the
  Computer Science AB: Quick Reference Guide

Note to instructors: You can supply the following implementations to your students. These implementations are supplied for convenience only; students are not required to know the classes for the test. 
 public class ArrayStack implements Stack 
{ 
  public ArrayStack() { array = new ArrayList(); } 
  public void push(Object x) { array.add(x); } 
  public Object pop() { return array.remove(array.size() - 1); } 
  public Object peekTop() { return array.get(array.size() - 1); } 
  public boolean isEmpty() { return array.size() == 0; } 

  private ArrayList array; 
} 

public class ListQueue implements Queue 
{ 
  public ListQueue() { list = new LinkedList(); } 

  public void enqueue(Object x) { list.addLast(x); } 
  public Object dequeue() { return list.removeFirst(); } 
  public Object peekFront() { return list.getFirst(); } 
  public boolean isEmpty() { return list.size() == 0; } 

  private LinkedList list; 
} 

public class ArrayPriorityQueue implements PriorityQueue 
{ 
  public ArrayPriorityQueue() { items = new ArrayList(); } 

  public void add(Object x) { items.add(x); } 

  public Object removeMin() 
  { Object min = peekMin(); items.remove(min); return min; } 

  public Object peekMin() 
  { 
    int minIndex = 0; 
    for (int i = 1; i < items.size(); i++) 
    { 
      if (((Comparable) items.get(i)).compareTo(items.get(minIndex)) < 0) 
      { 
         minIndex = i; 
      } 
    } 
    return items.get(minIndex); 
  } 

  public boolean isEmpty() { return items.size() == 0; } 

  private List items; 
}


Copyright © 2004 by collegeboard.com, Inc. and its licensors. All rights reserved. By visiting and using collegeboard.com, you agree to the Site Terms and Conditions and Privacy Policy. Contact us.