FIFO - First In First Out

Data structure to store and remove data
First data enqueued is the first data dequeued (FIFO)
- Think of it like a queue of people in a checkout line. First person to enter the line will be the first person to leave the line.
Standard methods for stacks
- enqueue() - Add an element to the end of the queue
- dequeue() - Remove an element from the front of the queue and return it
- isEmpty() - Returns whether or not the queue is empty
- size() - Returns the number of elements in the queue
- peek() - Returns the element at the front of the queue (doesn’t remove it)

Implementations of Queues

Using Arrays
- Arrays will have lower memory overhead compared to linked lists
- An array implementation usually uses a circular array
  - The data structure will keep track of the index of the front and back of the queue
  - If there isn’t another spot to add to, first check if we can loop back around to the front of the array
  - If we can’t loop back around to the front then we increase the size of the array
Using Linked Lists
- Because linked lists are resizable you don’t need to keep track of indices at all
- You have to keep track of the front and back queue nodes to enqueue onto and dequeue off of