Double Ended Queue aka Deque is a regular Queue Data Structure with additional property, elements can be added to or removed from either the front (head) or rear (tail)

Basic operations

  • Insert aka Enqueue, inserts element at rear and front of the queue
  • Remove aka Dequeue, retrieves and removes the rear and the front of the queue
  • Examine, retrieves, but does not remove, the rear and the front of the queue

Other operations

  • isEmpty returns true if no more items can be dequeued
  • isFull returns true if no more items can be enqueued
  • size returns the number of items on the queue

Implementation

You can implement a queue with either a Linked List, a Static Array (capacity restricted) or a Dynamic Array

Dequeue implementation example with Static Array