1.
204 Lecture 6
Data structures: stacks, queues,
trees, dictionaries
Data structures
• Correct and efficient representation of data and applicable
rules
– Stack: last in, first out discipline
– Queue: first in, first out discipline
• Double-ended queue (deque): general line discipline
– Heap: priority queue discipline
– Tree:
• Binary search tree (BST): ordered data, using a key
• Heaps are represented using binary tree
• Many other tree variations (B-tree, quadtree, AVL tree…)
– Set:
• Disjoint sets of elements, modeled as forest: set of disjoint trees
– Graph/network:
• Set of nodes and arcs (with costs)
– (Arrays are a simple data structure but are not as efficient nor
do they ensure correctness)
1
Stacks
Stack s
4 = Capacity -1
Top “c” 2 Push(“a”)
Push(“b”)
Top “b” 1
Push(“c”)
Top “a” 0
Pop() “c”
Top -1
Pop() “b”
Using a Stack
public class StackTest {
public static void main(String args[]) {
int[] array = { 12, 13, 14, 15, 16, 17 };
Stack stack = new Stack();
for (int i : array) {
[Link](i);
}
while (![Link]()) {
int z= (Integer) [Link]();
[Link](z);
}
}
}
// Output: 17 16 15 14 13 12
2
Stack, 1
import [Link].*;
public class Stack {
public static final int DEFAULT_CAPACITY = 8;
private Object[] stack;
private int top = -1;
private int capacity;
public Stack(int cap) {
capacity = cap;
stack = new Object[capacity];
}
public Stack() {
this( DEFAULT_CAPACITY );
}
Stack, 2
public boolean isEmpty() {
return (top == -1);
}
public void clear() {
top = -1;
}
3
Stack, 3
public void push(Object o) {
if (++top == capacity)
grow();
stack[top] = o;
}
private void grow() {
capacity *= 2;
Object[] oldStack = stack;
stack = new Object[capacity];
[Link](oldStack, 0, stack, 0, top);
}
Stack, 4
public Object pop()
throws EmptyStackException
{
if (isEmpty())
throw new EmptyStackException();
else {
return stack[top--];
}
}
// Java has Stack class that will be deprecated soon
// Java suggests using Deque for stack and queue
4
Stack uses and efficiency
• Applications
– Keep track of pending operations
• Tree branches not explored (branch and bound)
• Divide and conquer splits not completed/combined yet
• Hierarchical communications networks (e.g., MPLS)
– Physical stacks of items
– Expression evaluation (with precedence)
• Efficiency
– Pop() and push() are both O(1)
• Size of stack does not affect these methods
– Space complexity of stack is O(n)
Queues
A queue is a data structure to which you add new items at one
end and remove old items from the other.
Remove Add items
items here here
1 2 3 4 ... n-2 n-1 n n+1
5
Queue
Rear Rear Rear Rear
"a" "b" "c"
Front Front
Rear
"c" "d"
Unused! Front Run out of room!
Queue
Rear
"c" "d"
Front
Wrap around!
6
Ring Queue
Front points to
first element.
Rear points to
rear element.
Cap’y-1
Rear
Front "a" 0
1 4
2 3
"b"
Front "c" "d"
"a"
Front "b"
Queue
public class Queue {
private Object[] queue;
private int front;
private int rear;
private int capacity;
private int size = 0;
static public final int DEFAULT_CAPACITY= 8;
7
Queue Data Members
queue: Holds a reference to the ring array
front: If size>0, holds the index to the next
item to be removed from the queue
rear: If size>0, holds the index to the last
item that was added to the queue
capacity: Holds the size of the array referenced by queue
size: Always >=0. Holds the number of items on the queue
Queue Methods
public Queue(int cap) {
capacity = cap;
front = 0;
rear = capacity - 1;
queue= new Object[capacity];
}
public Queue() {
this( DEFAULT_CAPACITY );
}
public boolean isEmpty() {
return ( size == 0 );
}
public void clear() {
size = 0;
front = 0;
rear = capacity - 1;
}
8
Queue Methods
public void add(Object o) {
if ( size == capacity )
grow();
rear = ( rear + 1 ) % capacity;
queue[ rear ] = o;
size++;
}
public Object remove() {
if ( isEmpty() )
throw new NoSuchElementException();
else {
Object ret = queue[ front ];
front = (front + 1) % capacity;
size--;
return ret;
}
}
// See download code for grow() method and for QueueTest class
Queue uses and efficiency
• Queue applications:
– First in, first out lists, streams, data flows
– Buffers in networks and computers
– Physical queues
– Keep track of pending operations
• Tree branches not explored in branch-and-bound, etc.
– Label correcting shortest path algorithms
• Use a ‘candidate list’ queue that allows arbitrary insertions
• Queue efficiency:
– add() and remove() are O(1)
• Constant time, regardless of queue size
– Space complexity of stack is O(n)
• Where n is maximum queue size, not number of items processed
9
Tree definitions
Level
(distance from root)
0
a
b c d 1
e f g h i 2
...
Root: a Children: of a are b, c, d
Degree (of node): number of subtrees Parent: of g is b
b:3, c:0, d:2 Siblings: children of same parent: b, c, d
Leaf: node of degree 0: e, c Degree of tree: max degree of its nodes(3)
Branch: node of degree >0 Ancestors: nodes on path to root:
Depth: max level in tree g’s ancestors are b and a
Binary tree definitions
Level
0
1
2 3 1
4 5 6 7 2
...
Max nodes on level i= 2i Complete binary tree in array:
Max nodes in tree of depth k= 2k+1-1 Parent[i]= i/2
(full tree of depth k) LeftChild[i]= 2i
RightChild[i]= 2i+1
0
1 2 If root is node 0 (rather than 1):
Parent[i]= (i-1)/2
LeftChild[i]= 2i+1
3 4 5 6 RightChild[i]= 2i+2
… …
10
Tree Traversal
• We call a list of a tree's nodes a traversal if it lists
each tree node exactly once.
• The three most commonly used traversal orders
are recursively described as:
– Inorder: traverse left subtree, visit current node,
traverse right subtree
– Postorder: traverse left subtree, traverse right subtree,
visit current node
– Preorder: visit current node, traverse left subtree,
traverse right subtree
Tree traversal examples
root
g
b x
d w z
c v
Inorder: bcdgvwxz
11
Tree traversal examples
root
g
b x
d w z
c v
Postorder: cdbvwzxg
Binary Search Trees
• There are many ways to build binary trees with
varying properties:
– In a heap or priority queue, the largest element is on top.
In the rest of the heap, each element is larger than its
children
– In a binary search tree, the left subtree has nodes
smaller than or equal to the parent, and the right subtree
has nodes bigger than or equal to the parent
• We saw that performing an inorder traversal of such a tree
visited each node in order
• We’ll build a binary search tree in this lecture and
a heap in the next lecture
12
Writing a Binary Search Tree
• We’ll build a Tree class:
– One data member: root
– One constructor: Tree()
– Methods:
• insert: build a tree, node by node
• inorder traversal
• postorder traversal
• (we omit preorder)
• find: whether an object is in the tree
• print tree
Writing a BST, p.2
• We also build a Node nested class inside Tree:
– Three data members: data, left, right
• data is a reference to an Object, so our Node is general
data
Comparable
left right
– Our data Objects must implement the Comparable interface,
which has one method:
int compareTo(Object other)
– compareTo returns:
• An int < 0 if (this < other)
• 0 if (other equals this)
• An int > 0 if (this > other )
13
Writing a BST, p.3
– Node class also has a set of methods, all used by
corresponding methods in the Tree class:
• insertNode
• traverseInorder
• traversePostorder
• findNode
• printNode
– Methods are invoked on root node and then traverse the
tree as needed
Tree and Node Classes
Tree methods invoked on
Tree:
private Node root; Tree object; they call Node
public Tree() {root=null;} methods invoked on the
public void inorder() {…} root node object
public void postorder() {…}
public void insert(o) {…}
public boolean find(o) {…}
public void print() {…}
Node:
public Comparable data;
Tree t: public Node left, right;
public Node(o) {data=o;}
root r public void traverseInorder() {…}
public void traversePostorder() {…}
public void insertNode(n) {…}
public boolean findNode(o) {…}
public void printNodes() {…}
14
Tree class
public class Tree {
private Node root;
public Tree() {
root= null; }
public void inorder() {
if (root != null) [Link](); }
public void postorder() {
if (root != null) [Link](); }
public void insert(Comparable o) {
Node t= new Node(o);
if (root==null)
root= t;
else
[Link](t); }
Tree class, p.2
public boolean find(Comparable o) {
if (root== null)
return false;
else
return [Link](o);
}
public void print() {
if (root != null)
[Link]();
}
15
Node class: data, constructor
private static class Node {
public Comparable data;
public Node left;
public Node right;
public Node(Comparable o) {
data= o;
left= null;
right= null;
}
Traversal
public void traverseInorder() {
if (left != null) [Link]();
[Link](data);
if (right != null) [Link]();
}
public void traversePostorder() {
if (left != null) [Link]();
if (right != null) [Link]();
[Link](data);
}
16
Node class, insertNode
public void insertNode(Node n) {
if ([Link]([Link]) > 0) {
if (left==null)
left= n;
else
[Link](n);
}
else {
if (right == null)
right= n;
else
[Link](n);
}
}
// No ties allowed
insert() in Action
insert(20) 18
parent at end
of failed search
11 25
7 16 19 32
8 12 17 null 27 33
20
new node
29
17
find() in Action
1st iteration
find(19) 18
11 2nd iteration 25
7 16 19 32
8 12 17 27 33
29
Find
public boolean findNode(Comparable o) {
if ([Link](o) > 0) {
if (left== null)
return false;
else
return [Link](o);
}
else if ([Link](o) < 0) {
if (right == null)
return false;
else
return [Link](o);
}
else // Equal
return true;
}
18
Keys and Values
• If binary search trees are ordered, then they must be
ordered on some key possessed by every tree node.
• A node might contain nothing but the key, but it's often
useful to allow each node to contain a key and a value.
• The key is used to look up the node. The value is extra data
contained in the node indexed by the key.
Maps/Dictionaries
• Such data structures with key/value pairs are usually called
maps or sometimes dictionaries
• As an example, consider the entries in a phone book as
they might be entered in a binary search tree. The
subscriber name, last name first, serves as the key, and the
phone number serves as the value.
19
Maps
• Implementing tree structures with keys and values is a
straightforward extension to what we just did. The Node
contains the same members:
– Data, a reference to a Comparable object with key and value
– Left
– Right
• We add or modify methods to set or get the values
associated with the keys
– No change in logic
• Map example on next slides
– This could be improved by having find() return the Object
instead of a boolean whether it was found
– You’d then have to check if the object is null, etc.
– These are straightforward changes, but we show the simplest
implementation here
Phone class
public class Phone implements Comparable {
private String name; // Name of person (key)
private int phone; // Phone number (value)
public Phone(String n, int p) {
name= n;
phone= p;
}
public int compareTo(Object other) {
Phone o= (Phone) other;
return [Link]([Link]); // String compare
}
public String toString() {
return("Name: "+ name +" phone: "+ phone);
}
}
// This will be the object pointed to by ‘data’ in Node
20
MapTest
public class MapTest {
public static void main(String[] args) {
Tree z= new Tree();
[Link](new Phone("Betty", 4411));
[Link](new Phone("Quantum", 1531));
[Link](new Phone("Thomas", 6651));
[Link](new Phone("Darlene", 8343));
[Link](new Phone("Alice", 6334));
[Link]();
[Link]("Inorder");
[Link]();
[Link]("Postorder");
[Link]();
[Link]("Search for phone numbers");
[Link]("Find Betty? " +
[Link](new Phone("Betty", -1)));
[Link]("Find Thomas? " +
[Link](new Phone("Thomas", -1)));
[Link]("Find Alan? " +
[Link](new Phone("Alan", -1)));
}
} // TreeTestGeneric and TreeGeneric use Java 1.6 generics
Tree uses and efficiency
• Applications
– Data storage and search
– Optimization: search discrete alternatives (DP, B-and-B)
– Priority queues
– Shortest paths, spanning trees on graphs
– Basis in network simplex
• Efficiency
– insert(), delete(), find() are O(lg n) average case
• We don’t cover delete()—it’s straightforward but tedious
– Degenerate trees are O(n) but can be avoided with care
• Never build a tree in sorted order
• Choose a non-key field to sort input to build the tree
– AVL, red-black trees rebalance to avoid worst case
• Most of our trees will keep parent node, not
children this term
21
MIT OpenCourseWare
[Link]
1.204 Computer Algorithms in Systems Engineering
Spring 2010
For information about citing these materials or our Terms of Use, visit: [Link]