Queue

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

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

• Singly Linked List

  • Enqueue at tail
  • Dequeue at head