CS 245 Lecture 22 – Stacks and Binary Search Tree
Agenda
- what ?s
- the purpose of stacks and queues
- a postfix expression calculator
- binary search tree
TODO
- Watch a random YouTube video on stacks and queues. Read about Java’s Stack badness. Read about using stacks and queues for time management. 1/4 sheet.
Design This
- You are building a 2-D memory/matching game. When the user clicks on the screen, the clicked-upon card is flipped. What data structure would you use to facilitate this interaction?
- You are writing an application that provides a command-line interface to applications on the computer. When the user types “ls”, the application stored at /usr/bin/ls is run. When the user types “octave”, the application stored at /usr/local/bin/octave is run. What data structure would you use to facilitate this interaction?
- You have the finishing times from a large marathon. People are asking your application who the nth-place finisher was. What data structure would you use to facilitate this interaction?
- You are writing a web browser and want to know if a URL has been visited before. If so, you can color it differently. What data structure would you use to achieve this effect?
Program This
You’ve got an expression in “postfix” form:
- 1 2 + (which is 1 + 2)
- 3 6 * 5 – (which is 3 * 6 – 5)
- 60 12 / 2 ^ (which is (60 / 12) ^ 2)
Devise a plan to parse and evaluate such expressions.
Code
BinarySearchTree.java
package lecture22;
public class BinarySearchTree<K, V> {
private Node<K, V> root;
private int size;
public BinarySearchTree() {
root = null;
size = 0;
}
public int size() {
return size(root);
}
private int size(Node<K, V> root) {
if (root == null) {
return 0;
} else {
return 1 + size(root.left) + size(root.right);
}
}
public void add(K key,
V value) {
Node<K, V> nodeToAdd = new Node<K, V>(key, value, null, null);
if (root == null) {
root = nodeToAdd;
} else {
root.add(nodeToAdd);
}
++size;
}
public static class Node<K, V> {
private K key;
private V value;
private Node<K, V> left;
private Node<K, V> right;
public Node(K key,
V value,
Node<K, V> left,
Node<K, V> right) {
this.key = key;
this.value = value;
this.left = left;
this.right = right;
}
public void add(Node nodeToAdd) {
}
}
}
Haiku
Some race to the top
Some wander left, back, then right
Who wins on a tree?
Some wander left, back, then right
Who wins on a tree?