This preview shows page 1-2-21-22 out of 22 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 22 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 22 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 22 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 22 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 22 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

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 nordo they ensure correctness) 1Stacks Stack s 4 = Capacity -1 3 Top “a” “c” “b” 2 Push(“a”) 1 Push(“b”)Top Push(“c”)0Top “c” Top -1 Pop() 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) { stack.push(i); } while (!stack.isEmpty()) { int z= (Integer) stack.pop(); System.out.println(z); } } } // Output: 17 16 15 14 13 12 2Stack, 1 import java.util.*; 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; } 3Stack, 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]; System.arraycopy(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 4Stack 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. 1 2 43 ... nn-1n-2 n+1 Remove items here Add items here 5Queue "a" "b" "c" Front Rear Rear Rear Rear Front Rear "c" "d" FrontUnused! Run out of room! Queue "c" "d" Rear Front Wrap around! 6Ring Queue Front points to first element. Rear points to rear element. 0 1 2 3 4 Cap’y-1 Rear Front Front "b" "c" "d" "a" "a" "b" Front 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; 7Queue 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; } 8Queue 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 910 Tree definitions Root: a Degree (of node): number of subtrees b:3, c:0, d:2 Leaf: node of degree 0: e, c Branch: node of degree >0 Depth: max level in tree Children: of a are b, c, d Parent: of g is b Siblings: children of same parent: b, c, d Degree of tree: max degree of its nodes(3) Ancestors: nodes on path to root: g’s ancestors are b and a Max nodes on level i= 2i Max nodes in tree of depth k= 2k+1-1 Complete binary tree in array: Parent[i]= i/2 LeftChild[i]= 2i RightChild[i]= 2i+1 If root is node 0 (rather than 1): Parent[i]= (i-1)/2 LeftChild[i]= 2i+1 RightChild[i]= 2i+2 a db gf ih c e Level (distance from root) 0 1 2 ... Binary tree definitions 1 32 54 76 Level 0 1 2 ... (full tree of depth k) 0 21 … … 43 65Tree 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 g b x d w z vc Inorder: b c d g v w x z root 11Tree traversal examples g b x d w z vc Postorder: c d b v w z x g root 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


View Full Document

MIT 1 204 - Lecture notes

Download Lecture notes
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Lecture notes and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Lecture notes 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?