Queue (ADT)

A queue is a data structure similar to a stack, but elements are inserted from one end and removed from the opposite: First in; first out (FIFO). In contrast, a stack inserts and removes from the same end.

Examples:

• Waiting in line

Functions

• int size() — Returns how many items are in the queue.
• bool isEmpty() — Returns whether the queue is empty (i.e. size is 0).
• void enqueue(Object o) — Puts an object $o$ at the end of the queue.
• Object dequeue() — Removes the object at the front of the queue and returns it.
• Object front() — Peeks at the front item without removing it.

Implementations

Array-based (Fixed; Circular)

• Create an array of fixed size $N$
• enqueue elements on the right; wrap to the far left if we reach the right boundary of the array
• Remove elements from
• Keep two pointers to the front $f$ and end $e$ items

Note:  if (e + 1) mod N = f, then the queue is full.

class ArrayQueue {
/* ... */

  int size() { return (N-f+e) % N; }

  bool isEmpty() { return f==e; }

  Object dequeue() {
    if (isEmpty()) throw new EmptyStackException();
    else return S[t-- + 1];
  }

  void enqueue(const Object& o) {
    if (size() == N-1) throw FullStackException();
    else {
      Q[r] = o;
      r = (r+1) % N
    }
  }
};

Array-based (Doubling)

We can use a circular array, but when it fills up, follow these steps:

1. Create a new array that is twice as large as the original array
2. Remove the items in queued order from the smaller array and put them in the new larger array
3. Delete the smaller array

Linked-List

Using a singly-linked-list that points to the right, we must keep track of the head and tail with pointers. New items can be enqueued on the right (tail) and dequeued from the left (head)

Analysis

See Amortized Time and Asymptotic Analysis for more information.

	Array (fixed)	Array (doubling)		List
enqueue()	$O(1)$	worst:	$O(n)$	$O(1)$
		best:	$O(1)$
		avg:	$O(1)$
dequeue()	$O(1)$	$O(1)$		$O(1)$