Transcript 14 StacksQueuesSetsMaps - Rose

CSSE221: Software Dev. Honors
 Announcements
Pass in Homework 5 now
 Questions on Cars, Trucks, Trains?
 Homework 6 and Markov posted soon:


do team sign-up for Markov.
Day 14
This week: Markov

Monday:
Stacks and Queues
 Sets, Maps, and PriorityQueues


Tuesday:
Some pros and cons of various data structures
 Brief example of file I/O
 Introduction to Markov, a cool statistical text
program with lots of data structures


Thursday:

Exam 1
Stack





LIFO (last-in-first-out).
Push [addBack]
pop [removeBack/“topAndPop”]
peek [get(back--); ]
Many applications, such as the implementation
of (recursive) method calls and “undo”
functions.
Can be implemented using an
ArrayList (last element in ArrayList
is top of Stack) or a LinkedList
(first element in LinkedList is top of
stack). Which is better?
push, pop, and peek are all constanttime O(1) operations.
Queue



Operations: offer [enqueue], poll [dequeue], peek.
FIFO (first-in-first-out).
Applications include simulations and operating systems.
offer, poll, and peek are all
constant-time operations.
Can be implemented using an ArrayList (treat positions as a circle)
or a LinkedList (first element in LinkedList is front of queue, last
element is rear of Queue). More details next slide.
Array
implementation
of a queue
What if we run out of
room?
LinkedList implementation of a
queue
Demo
A tale of two interfaces: Set<E>…




A collection with no duplicates
If obj1 and obj2 are both in the set, then
obj1.equals(obj2) returns false.
Subinterface: SortedSet
Not quite a mathematical set (no intersection or
union methods)
“Bob”, “Flo”, “Gary”, “Lisa”, “Marie”
…and Map<K,V>
HashMap<Integer, String> map =
new HashMap<Integer, String>();

map.put(123456789, “”Bill Smith”);
map.put(987654321, “Darla Clive”);
An object that maps keys to values.
Duplicates?


Keys
123456789, 987654321, 102934857
NO
Values
OK
“Bill Smith”, “Darla Clive”

A map cannot contain duplicate
keys; each key can map to at most
one value.
V get(Object key)
Multiple keys can have the same
value
Other operations:
 put(K key, V value)
 containsKey(Object key)
 containsValue(Object value)
 V remove(Object key)
TreeSets and TreeMaps
…are java.util implementations of SortedSet and
Map.
 Ordered elements.
 In a tree, average time is O(log n),

and with complex algorithms, worst case can also be
O(log N)

Also support taking ordered subsets from head,
tail, or interior of set or map

More details in CSSE230…
HashSets and HashMaps
…are java.util implementations of Set (not
SortedSet) and Map.
 Average time for lookup, insertion, or deletion is
O(1).
but worst case is O(N).
 A quick view of how it works:

hashCode function maps object to an integer, which is used
to find an index into an array.
 Collision resolution.
 Fast search, but unordered.



Need to implement .equals() and .hashCode()
More details in CSSE230…
PriorityQueue class





Similar to a queue, but each item has an associated priority.
Only the item with minimum priority is accessible.
Allows an object to “cut” in line if lower priority
Elements need to be comparable
Operations:



findMin(peek) (O(log n))
deleteMin(poll) (O(log n))
insert(offer) (O(1))


Underlying data structure: a binary heap (another
shameless plug for CSSE230)
Speaking of CSSE230

Given the choice, you should take CSSE230 after this
Winter. Why?

Less overlap with 221 and you’ll do a cool project
Demo