Exam 2 Review

Stacks and queues

• Basic operations
• Semantics
• Implementation
  
• Deques and priority queues
  

Arithmetic expressions

• Infix, postfix, and prefix notation
• Postfix evaluation algorithm
• Infix to postfix algorithm

The Map interface

• Basic operations
• Semantics
• Implementation

Object-oriented design and analysis

• UML diagrams.
• Design patterns
  

Trees

• Basic terminology
• Binary trees
• Tree traversals
• Expression trees
• Implementation
• Tree iterators
• Cloning a binary tree
• Binary search trees
• Search and insert algorithms
• Binary search trees as Maps
• Balanced binary search trees
• AVL trees
• Red-black trees
• Nonbinary trees
• Implementation
• Tries

What you should be able to do

• Apply algorithm analysis techniques to problems involving stacks, queues, and trees.
• Write code using the data structures we've studied.
• Write code to implement the data structures we've studied.
• Carry out basic algorithms by hand.