Queues

First in first out (FIFO)

ADT

• Data
  • Items
  • Number of items
  • Front and back
• Operations
  • enqueue(item): Inserts element in back of queue
  • dequeue(): Removes and returns from front of queue
  • size()
  • isEmpty()

Implementations

Array

• Characteristics
  • Fixed Size
  • Stores similar elements
  • Access through front index
• Performance
  • enqueue(item): O(1)
  • dequeue(): O(1)
  • size(): O(1)
  • isEmpty(): O(1)
• Pros/Cons
  • Pros: Constant time to add and remove elements
  • Cons:
    • Limited space
    • Rightward drift problem

Circular Array

• Has front and back of queue go around in a circle
• Uses the mod operator
• Prevents the rightward drift problem

Linked List

• Characteristics
  • Flexible Size
  • Stores Similar Elements
  • Access through front pointer
• Performance: Same as array for doubly linked with tail
• Pros/Cons
  • Pros
    • Constant time to add and remove elements
    • Variable size
  • Cons
    • More Memory

Use Cases

• Print queue
• Task scheduling by OS
• Packet forwarding by routers