ADT Queue

A Queue (pronounced cue) is a list of items but this time when I add something to the list, it is added to the back of the line. When a retrieve an item from the queue, I grab it from the front of the line. This is known as a First-In First-Out (FIFO) data type. Think of it as waiting in line to by tickets. The person who gets to the line first is the first person to get a ticket. Everyone else lines up after them and is called in turn of when they joined the line.

A queue has the following methods:

• enqueue(Object item)  <-- add an item to the queue
• dequeue()  <-- retrieve the first item from the queue
• peek()  <-- take a look at the first item in the queue
• size()  <-- how many items are in the queue
• isEmpty()  <-- returns whether the queue is empty or not

Deque Implementation

A deque is a specific implementation that uses a doubley linked list (a list that has a pointer to the next node and the previous node). This means we have direct access to both the front and the back of the list at the same time. This makes it a great implementation to use because all of the operations can be done in O(1) time.