|
|
 |
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;
}
|
