Double Ended Queue (Deque)

Double Ended Queue (Deque)

A Deque (pronounced 'deck') stands for Double-Ended Queue. It is a generalized linear data structure that permits element insertion and deletion at both the Front and Rear ends.

Types of Deques

1. Input-Restricted Deque:

   • Insertion is allowed only at one end (usually the rear).
   • Deletion is allowed at both ends (front and rear).

2. Output-Restricted Deque:

   • Insertion is allowed at both ends (front and rear).
   • Deletion is allowed only at one end (usually the front).

---

Modulo Circular Wrap Arithmetic

To avoid wasting array memory, a Deque is usually implemented circularly using modulo wrap logic:

1. Insert Front:

   • Check if full: ((front == 0 && rear == MAX - 1) || front == rear + 1).
   • If empty: set front = 0, rear = 0.
   • Wrap left: if front == 0, set front = MAX - 1.
   • Normal decrement: front--.
   • Store: arr[front] = value.

2. Insert Rear:

   • Check if full.
   • If empty: set front = 0, rear = 0.
   • Wrap right: if rear == MAX - 1, set rear = 0.
   • Normal increment: rear++.
   • Store: arr[rear] = value.

3. Delete Front:

   • Check if empty: front == -1.
   • Extract: value = arr[front].
   • If 1 element left (front == rear): reset pointers to -1.
   • Wrap right: if front == MAX - 1, set front = 0.
   • Normal increment: front++.

4. Delete Rear:

   • Check if empty.
   • Extract: value = arr[rear].
   • If 1 element left: reset pointers to -1.
   • Wrap left: if rear == 0, set rear = MAX - 1.
   • Normal decrement: rear--.