Deque (Double-Ended Queue)

A deque (double-ended queue) allows insertion and removal from either the front or the rear — it doesn’t follow the FIFO rule.

Types of Deque

• Input-restricted deque — input is restricted to a single end, but deletion is allowed at both ends.
• Output-restricted deque — output is restricted to a single end, but insertion is allowed at both ends.

Operations

In a circular array, once full, insertion wraps back to the beginning. In a linear array, once full, no more elements can be inserted — each operation below throws an “overflow” message in that case.

Setup: take an array (deque) of size n, with front = -1 and rear = 0.

Insert at the Front

1. Check the position of front.
2. If front < 1, reinitialize front = n - 1 (last index).
3. Otherwise, decrease front by 1.
4. Add the new key into array[front].

Insert at the Rear

1. Check if the array is full.
2. If full, reinitialize rear = 0.
3. Otherwise, increase rear by 1.
4. Add the new key into array[rear].

Delete from the Front

1. Check if the deque is empty.
2. If empty (front == -1), deletion can’t be performed (underflow).
3. If there’s only one element (front == rear), set front = -1 and rear = -1.
4. Else if front is at the end (front == n - 1), wrap front = 0.
5. Otherwise, front = front + 1.

Delete from the Rear

1. Check if the deque is empty.
2. If empty (front == -1), deletion can’t be performed (underflow).
3. If there’s only one element (front == rear), set front = -1 and rear = -1 — otherwise follow the steps below.
4. If rear is at the front (rear == 0), wrap rear = n - 1.
5. Otherwise, rear = rear - 1.

Check Empty

front == -1 means the deque is empty.

Check Full

front == 0 && rear == n - 1, or front == rear + 1, means the deque is full.

Time Complexity

All operations above run in constant time, O(1).