csc data structures exam 2

Stack

super-unfair – new items go on top AND we process off the top – recursion works like this (the bottom is the oldest recursive call) which is big

you want to use linked lists unless a case can be made for an array

Array is an implementation you can use for both

Queue

new items go in the back, items to process come off the front – this is very fair and simulates waiting in line for your turn

you want to use linked lists unless a case can be made for an array

Array is an implementation you can use for both

Circular Arrays II

Very common one where we are cycling through some data and don’t want to have to detect the tail -Or representing something like an analog clock

When you want to increase a counter (say, the next open spot) in an array of length n, do %n at the end!

ArrayQueue

Uses a circular array that “unwinds” on making a bigger array (ensureCapacity)

Preorder Traversal

root, left, right

Post order traversal

left, right, root

In order traversal

left, root, right

Heaps

-Always O(logn)

-Always complete

-Min() – O(1) to find min at top of heap

-Insert() – O(logn) as you put it at the bottom then heapify up

-Remove() – O(logn) as you swap the root with the last note, heapify down