Queue

A queue is a linear, abstract, data structure in which items are accessed in a First In First Out (FIFO) order. It can be likened to a queue of people, where the first person to join the queue is served first. Queues are used in ‘breadth-first’ style algorithms, such as breadth first search and level-order tree traversal.

Definition §

• A collection of items accessed in First In First Out (FIFO) order
• Only the front can be viewed (similar to stacks)
• Adding items is referred to as enqueuing
• Removing items is referred to as dequeuing
• The first item that was added to a queue is also the first item to leave it

ADT Signature §

name Queue; 
import elem, boolean; 
ops:
	newQueue : → queue; 
	enQueue : queue × elem → queue; 
	deQueue : queue → queue; 
	front : Queue → elem; 
	isEmpty : Queue → boolean;
	etc.

Implementations §

Unsorted Array §

We can use an unsorted array for queues, where enqueue is adding elements to the end of the array, and dequeue is removing elements from the beginning (without shifting elements). This saves us time taken by shifting, but adds an extra problem:

Because we are not shifting elements, we have ‘gaps’ in the array, so we need a counter to store the queue start and end, which is different from the array start and end. Also, we need a circular ring buffer to make optimal use of storage#todo .

Basic Operation: Array Access

Assumptions:

• $A$ = The underlying array used to store the stack
• $n$ = The number of elements in the array
• $front$ = The index of ‘front’ of the queue. The element at this index is the first to be dequeued.
• $back$ = The index of ‘back’ of the queue. Queued elements are added after this index.

Initially, set $front=-1$ and $back=-1$

Operation	Worst Case (WC)	Best Case (BC)	Average Case (AC)	Case descriptions
Queue	$\Theta (1)$	$\Theta (1)$	$\Theta (1)$	Insert at $A[back+1]$, (so after the last element). If $back+1>n-1$, then we need to ‘wrap around’. Then, increment $back$ by 1. Array insertion is constant time (we are not ensuring it is sorted)
Dequeue	$\Theta (1)$	$\Theta (1)$	$\Theta (1)$	Delete at index $front$, and then increment $front$ by 1.If $front>n-1$, we need to ‘wrap around’. We are not shifting elements, so this is constant time.
Peek	$\Theta (1)$	$\Theta (1)$	$\Theta (1)$	Return $A[front]$. Constant time, always

Singly Linked List §

A linked list is an alternative, easier approach to implement a queue. It implements enqueue by inserting to the tail, and dequeue by deleting from the head. Alternatively, we can enqueue by inserting to the head, and dequeue by deleting from the tail.

Note how this differs from a linked list implementation of a stack: A list has different locations for where elements get inserted to and deleted from (either head/tail or tail/head), while a stack does it on the same location (either head/head or tail/tail).

Basic Operation: Traversing to the next node of a linked list.

Assumptions:

• $L$ = Linked list
• $head$ = Head of the list and queue
• $tail$ = Tail of the list and queue

Operation	Worst Case (WC)	Best Case (BC)	Average Case (AC)	Case descriptions
Enqueue	$\Theta (1)$	$\Theta (1)$	$\Theta (1)$	Equivalent to insertion at tail/head of a linked list, which always takes constant time
Dequeue	$\Theta (1)$	$\Theta (1)$	$\Theta (1)$	Equivalent to deletion from the head/tail of a linked list, which is also constant time.
Peek	$\Theta (1)$	$\Theta (1)$	$\Theta (1)$	Getting the tail/head is always constant time.

#todo

• Unsorted Array

  • Enqueue: Put at end, $n++$
  • Dequeue, use circular ring buffer

• Singly Linked List

  • Enqueue at tail
  • Dequeue at head

Uses §

• Breadth First Search Algorithm
• Binary Tree In-order Traversal