Recitation 11: 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 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.
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.
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
class Utils { <T> ArrayList<T> reverse(ArrayList<T> source) { ... } }
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
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(); }
interface Iterable<T> { Iterator<T> iterator(); }
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.
// In ExamplesDeque void testDequeIteration(Tester t) { Deque<String> dq = new Deque<String>(); dq.addAtTail(", "); dq.addAtHead("Hello"); dq.addAtTail("world!"); String msg = ""; for (String s : dq) { msg = msg.concat(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
class BreadthFirstIterator implements Iterator<Integer> { Queue<NumNode> todoList = new Queue<NumNode>(); }
The hasNext method should look at the todo list, and determine if it is empty or not.
Deque an NumNode from the todo list. It will eventually return the value of this node.
If the left child of the node is not a NumLeaf, enqueue it in the todo list.
If the right child of the node is not a NumLeaf, enqueue it in the todo list.
Return the value of the node.
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 right child before the left child (why?).
Test both of these iterators.