On this page:
1 Stacks and Queues
1.1 Practice puzzle
2 Binary trees
3 Iterators and Iterables
4 Challenge:   iterating through a binary tree

Lab 10: Working with Stacks, Queues and Trees

Goals: This lab will practice fundamental algorithms using stacks, queues, and trees. It will also practice working with iterators (which in turn may use stacks and queues).

Copy your implementation of Deques from Assignment 7: Doubly-linked lists into a new project.

1 Stacks and Queues

Stacks and Queues are data structures that look much like mutable lists, where we restrict how we add and remove items to and from the list.

A stack is a mutable list where we are permitted only to access the head of the list: we can add an item to the head of the list, or we can remove an item from the head of the list, and we can determine if a stack is empty. The canonical example of stacks are piles of dishes: we can only access the topmost dish, and to access the bottom plates we have to remove the top ones first. Stacks are described as “last-in-first-out”: the last item that was added to the stack is the first one that gets removed.

In a separate file from your Deque implementation, implement the following class:
class Stack<T> {
Deque<T> contents;
void push(T item); // adds an item to the head of the list boolean isEmpty();
T pop(); // removes and returns the head of the list }

You are not to modify the implementation of Deque at all (except to fix bugs in your code, if you find any). In particular, you are not to rely on the particulars of Sentinels and Nodes and such; treat Deque as an opaque black box that you can only manipulate via its methods.

A queue is a mutable list where we are permitted only to add items to the tail of the list, remove items from the head of the list, and determine if the queue is empty. Queues are described as “first-in-first-out”: the first item that gets added to a queue is the first one that gets removed. The canonical example of a queue is waiting on line: people enter the line from the back, shuffle forward until they are at the front of the line, and exit the line at the front.

Implement the following class:
class Queue<T> {
Deque<T> contents;
void enqueue(T item); // adds an item to the tail of the list boolean isEmpty();
T dequeue(); // removes and returns the head of the list }

1.1 Practice puzzle

Using two for-each loops and either a stack or a queue as a temporary storage space (only one of them will work), define the method that reverses an ArrayList:
class Utils {
<T> ArrayList<T> reverse(ArrayList<T> source) { ... }
If you use a stack, then you can only use the methods push, pop and isEmpty; if you use a queue, you can only use the methods enqueue, dequeue and isEmpty.

2 Binary trees

A binary tree is either a Leaf, or a Node containing a value, a left subtree and a right subtree. Define the (empty) interface INumBinTree and classes NumNode and NumLeaf. For now, we will only work with trees containing numbers as their values.

Define a helper method isLeaf() that returns true for NumLeaf objects. Define a helper method NumNode asNode() that returns NumNodes but throws an error on NumLeaf values. We’ll need these two helpers later.

A binary search tree is a binary tree where every value in the left subtree of a NumNode is less than the value at the node, every value in the right subtree of a node is greater than the value at the node, and each subtree is itself a valid binary search tree. (For now, assume there are no duplicate values anywhere in the tree.) This property is called an invariant, because it is a requirement that must always be maintained.

Note that all binary search trees are binary trees, but not all binary trees are binary search trees. Therefore, define the method boolean validBST() in the INumBinTree interface that returns true if the tree upholds the binary search tree invariant.

Define the method INumBinTree insertBST(int num) that produces a new binary search that results from inserting a new value into this binary search tree. You should assume in your implementation that the binary search tree invariant holds on the current tree, and you must ensure that the invariant holds on the output tree.

3 Iterators and Iterables

The Iterator<T> interface is responsible for producing a sequence of T values, and the interface is defined by Java as
interface Iterator<T> {
// returns true if there's at least one value left in this iterator boolean hasNext();
// returns the next value and advances the iterator T next();
// IGNORE THIS FOR NOW void remove();
Since you must implement all three methods to properly implement this interface, to implement remove(), you should throw new UnsupportedOperationException();.

The Iterable<T> interface asserts that a given object can be iterated to produce a sequence of T values. It is defined by Java as
interface Iterable<T> {
Iterator<T> iterator();
Classes that implement this interface must supply some Iterator object that can then be used to iterate over themselves.

In your implementation of Deque, implement a class ForwardDequeIterator<T> that iterates through the Nodes and Sentinel of a Deque. It should contain a field curr that is a reference to an ANode.
  • If curr refers to a Node, then hasNext should return true, and next should return the value in that Node. It should also update curr to refer to the next node in the Deque.

  • If curr refers to the Sentinel, then hasNext should return false.

Revise the definition of Deque to say it implements Iterable<T>. Implement the iterator() method to return a new ForwardDequeIterator.

If you’ve built your iterator correctly, then you should now be able to use a Deque in a for-each loop:
// In ExamplesDeque void testDequeIteration(Tester t) {
Deque<String> dq = new Deque<String>();
dq.addAtTail(", ");
String msg = "";
for (String s : dq) {
msg = msg.append(s);
t.checkExpect(msg, "Hello, world!");

Implement another class ReverseDequeIterator<T> that iterates backward through the Nodes and Sentinel of a Deque. (Hint: it should be just a tiny change from the forward iterator!) Add a method to Deque to return a reverse-iterator (since you already have a method that returns a forward-iterator).

Write a while loop that tests using a reverse iterator on a Deque.

4 Challenge: iterating through a binary tree

To iterate through a binary tree, we have to maintain a “todo list” of nodes in the tree that we have yet to process. Define a class BreadthFirstIterator that implements Iterator<Integer>:
class BreadthFirstIterator implements Iterator<Integer> {
Queue<NumNode> todoList = new Queue<NumNode>();
The constructor for a BreadthFirstIterator should take a single INumBinTree and enqueue it in the worklist, if it is not a NumLeaf.

The hasNext method should look at the todo list, and determine if it is empty or not.

The next method should:
  • Deque an NumNode from the todo list. It will eventually return the value of this node.

  • If the right child of the node is not a NumLeaf, enqueue it in the todo list.

  • If the left child of the node is not a NumLeaf, enqueue it in the todo list.

  • Return the value of the node.

(Why do we need to enqueue the right child before the left child?)

Revise the INumBinTree interface to extend Iterable<Integer>. Implement Iterator<T> iterator() on NumNode and NumLeaf, to return a BreadthFirstIterator as appropriate. If you’ve implemented it correctly, you should be able to use a INumBinTree with a for-each loop.

Define another class DepthFirstIterator, which is just like BreadthFirstIterator but with two changes: it should use a Stack instead of a Queue, and it should add the left child before the right child (why?).

Test both of these iterators.