FIFO Queue - Circular array

Instance variables

Constructors

• Set elementData to an array of default capacity

• Set elementData to an array of param

int getRear()

• If size equals 0 then there is no rear

• Front index + the number of elements gives the rear—we subtract 1 because frontIndex is already an element

boolean Offer(E item)

• ensure capacity can hold 1 more element

• Get the rear index

• Edge—If the list is empty we put item at front index

• Normal case—we put item 1 after rear

E poll()

• Store the element at front index

• Set it to null

• Increment front index—if next index is equal to capacity, out of bounds by 1

• Edge case—if we removed the last element, fix front index

E peek()

• Store the element at front index

• Return that element without removal

boolean contains(Object o)

• Linear time operation—start at front index

• Iterate for each element in array—not null

• Increment index each iteration—if it equals capacity, wrap around

boolean add(E e)

Send over to offer method

boolean remove(Object o)

• Not supported—we don’t arbitrarily remove elements from a queue stack

boolean addAll(Collection<E> c)

• Create iterator with collection

• While iterator has next—send over next to offer

Object[] toArray()

• Make a new object array

• Linear time operation—start at front index

• Iterate for each element in elementData—not null

• Put that element index in new array

• Increment index

void clear()

• Linear time operation—start at front

• Set each index to null—only necessary indices

• Increment index

void ensureCapacity(int minCap)

• Check if capacity is less than param capacity

• Create a new capacity

• Double check if it’s big enough

• Make a new arrray of old array

• Store front index—and set variable to 0

• create new array with new capacity

• Linear time operation—start at front of old array

QueueIterator class

• Instance variable of number returned elements

• hasNext()

  • Checks if size is greater than number of elements returned

• next()

  • Checks if there is a next element

  • Stores element at the index of—frontIndex plus number of elements returned

  • Increments and returns