Lecture 8 - hopefully this works

P2 covers Priority Queues

Pairing Heap papers must be read, not covered in lecture

Stacks using Arrays

• Pointer (top_ptr) points to last element of array
• Push(object), O(1)
  • Amortized Complexity
• Pop(), decrement top_ptr O(1)
• Object () dereference O(1)
• size() O(1)
• empty() O(1)

Stacks using Linked Lists

• Push(object) O(1)
• Pop() O(1)
• Object ⊤() O(1)
• Size() O(1)

• Empty() O(1)

• base_ptr?

  • top_ptr?

Queue Container

• Supports insertion and removal in FIFO order
• FIFO = First in, First out
  • Whoever gets there first, gets out first

Queue Examples

• Office Hours

Queues Using Arrays: Circular Buffer

• Cycle back to the beginning when you get to the end of the array

• Ex. Front and back point to first element

  • Push item, back gets incremented
  • Pop item, front gets incremented

  • Enqueue O(1)

  • When you get to the end of the array, you wrap around and back points to the first element

  • Once front and back point to the same element (line up), call grow and copy the items (in order?) in the new copy, but with a buffer in between front and back pointers

  • Dequeue O(1)

  • Object &front() O(1), stop fronting

  • size() O(1)

  • empty() O(1)

Queues using Linked Lists:

• Push() O(1)
• Pop() O(1)
• Object &front(), stop fronting
• Size() O(1), if you keep track of size separately
• Empty() O(1)

Enqueue adds an item to the array

Deque: Queue and Stack in One (Double-ended Queue)

• Used parts circular array idea
• vector of vectors (not really)

Deque example, not sure about the movement of end

Stacks and Queues in STL

Vectors and Deques are better than Linked Lists in most ways

• Linked LIsts are better in random_insert and random...remove, fill...front

Priority Queue

Highest Priority = Lowest Number in this case (and usually)

Items returned in the order of the priority

• Each datum paired with a priority value (comparable number)
  • Should be able to compare values (<)
  • In project, we override < to customize