Using Stacks, Queues, and Priority Queues

As of this writing, the AP AB exam will test the use of the following items for stacks, queues, and priority queues:

• The Stack class (which implements the List interface)
• The Queue interface and its implementing class, LinkedList
• The PriorityQueue class (which also implements the Queue interface)

All of these collections are generic and are included in the java.util package of Java 5.0. Here are some examples of their use:

Stack<String> stk = new Stack<String>();

Queue<String> qu = new LinkedList<String>();

Queue<String> priqu = new PriorityQueue<String>();

for (int i = 10; i >= 1; i--){    
   String str = "" + i;     // Insert "10" "9" "8" "7" "6" "5" "4" "3" "2" "1"        
   stk.push(str);        
   qu.add(str);        
   priqu.add(str);   
}

while (! qu.isEmpty()){    
   String str = stk.pop();  // Pop    "1" "2" "3" "4" "5" "6" "7" "8" "9" "10"
   str = qu.remove();       // Remove "10" "9" "8" "7" "6" "5" "4" "3" "2" "1" 
   str = priqu.remove();    // Remove "1" "2" "3" "4" "5" "6" "7" "8" "9" "10"   
}

---

Using Iterators

AP AB students must know how to use an iterator and a list iterator. In Java 5.0, ists, sets, stacks, queues, and priority queues all indirectly implement java.util's Collection interface. This interface in turn extends the Iterable interface, which includes the iterator method. Thus, essentially all collections must implement an iterator method which returns an iterator. Like the collections, iterators are also generic. Here is an example of the use of an iterator with a priority queue:

Queue<String> priqu = new PriorityQueue<String>();

// Add some strings to the priority queue

Iterator<String> iter = priqu.iterator();
while (iter.hasNext()){
   String str = iter.next();
   // Do something with str
} 

---

Implementing Generic Collections: A True Stack

Although the AP exam will not require students to define generic collections, there are many reasons why it's a useful thing to know how to do. First, java.util's resources for stacks, queues, and priority queues all have flaws. Because they all indirectly implement the List interface, they can all be made to behave like lists. Second, the PriorityQueue class uses a heap-based implementation that does not guarantee FIFO ordering of elements with equal priorities. Third, some forms of binary search trees and heaps will continue to be tested on the AP AB exam, and most students taking a college-level CS2 course would learn how to implement these structures, which are not included in java.util. Finally, the implementation strategies used for the collection classes provide wonderful case studies in object-ortented software design and in performance analysis.

To implement a generic collection, the student must be able to specify formal type parameters and type variables. This is not complicated for simple collections, such as stacks. Here is the code for an interface called TrueStack, which specifies the operations tested on the AP AB exam:

public interface TrueStack<E> extends Iterable<E>{
   public boolean empty();
   public E peek();
   public E pop();
   public void push(E element);
   public int size();
}

The TrueStack interface extends the Iterable interface, thus requiring all stack implementations to include an iterator method (the reason for this will become clear when you examine the enhanced for loop). The type variable E is a placeholder in this code for the actual element type used when a stack variable is declared.

The class TrueArrayStack, whose code follows, is an array-based implementation of our TrueStack interface. TrueArrayStack contains an instance of ArrayList, so all of the operations are straightforward.

import java.util.*;

public class TrueArrayStack<E> implements TrueStack<E>{

   List<E> list = new ArrayList<E>();

   public boolean empty()        {return list.isEmpty();}
   public E peek()               {return list.get(size() - 1);}
   public E pop()                {return list.remove(size() - 1);}
   public void push(E element)   {list.add(element);}
   public int size()             {return list.size());}
   public Iterator<E> iterator() {return list.iterator();}
}

The programmer now has resources for a "safe" stack, whose operations are restricted to those commonly associated with stacks. The interface and the class can be subsituted for the java.util.Stack class in the earlier example without any other changes to the code:

TrueStack<String> stk = new TrueArrayStack<String>();

Queue<String> qu = new LinkedList<String>();

Queue<String> priqu = new PriorityQueue<String>();

for (int i = 10; i >= 1; i--){    
   String str = "" + i;     // Insert "10" "9" "8" "7" "6" "5" "4" "3" "2" "1"        
   stk.push(str);        
   qu.add(str);        
   priqu.add(str);   
}

Resources for safe and restricted queues and priority queues can be developed in a similar manner.