Deque

A regular queue is strict about direction: insert only at the rear, remove only at the front. A deque (double-ended queue) drops that restriction, both ends allow insertion and deletion.

Deque vs queue

A plain queue is a deque with two of its four operations never used (INSERT_FRONT and DELETE_REAR). Every queue is really a restricted deque; a deque is the more general structure.

Insertion and deletion at both ends

Unlike a plain queue, both ends here are active: an element can be inserted or removed at FRONT, and independently, an element can be inserted or removed at REAR.

Types of deque

Not every deque implementation allows full freedom at both ends. Two restricted variants show up in practice and in exam questions:

An input-restricted deque only lets new elements in from one end, but either end can be used to remove elements. An output-restricted deque is the mirror image: elements can come in from either end, but only leave from one.

Operations

Each end gets its own insert and delete, four operations total.

INSERT_FRONT(x): insert at front

If FRONT == -1
    FRONT = 0
    REAR = 0
Else if FRONT == 0
    return OVERFLOW
Else
    FRONT = FRONT - 1
 
A[FRONT] = x

The middle branch is the array's physical limit: if FRONT is already at index 0, there's no earlier index to shift into in a plain array, so this reports overflow. (Some implementations shift existing elements right instead of reporting overflow here, but that trades an O(1) insert for an O(n) one, check which the algorithm or question you're following expects.)

INSERT_REAR(x): insert at rear

If REAR == n - 1
    return OVERFLOW
Else if REAR == -1
    FRONT = 0
    REAR = 0
Else
    REAR = REAR + 1
 
A[REAR] = x

This mirrors INSERT_FRONT: the overflow check happens first (no room past the last index), and the empty-deque case initializes both pointers together, same reasoning as a plain queue's first insertion.

DELETE_FRONT(): delete from front

If FRONT == -1
    return UNDERFLOW
 
value = A[FRONT]
 
If FRONT == REAR
    FRONT = -1
    REAR = -1
Else
    FRONT = FRONT + 1
 
return value

DELETE_REAR(): delete from rear

If REAR == -1
    return UNDERFLOW
 
value = A[REAR]
 
If FRONT == REAR
    FRONT = -1
    REAR = -1
Else
    REAR = REAR - 1
 
return value

Both delete operations reset both pointers to -1 when the element being removed was the last one left, same reasoning used for a plain queue: once the deque is empty, there's no meaningful position left for either pointer to hold.

IS_EMPTY and IS_FULL

IS_EMPTY(): return FRONT == -1
IS_FULL():  return REAR == n - 1

Worked state transitions

Starting from an empty deque of capacity 4:

Initial:              FRONT = -1, REAR = -1  (empty)
 
INSERT_FRONT(10):     [10]                    FRONT = 0, REAR = 0
INSERT_REAR(20):      [10][20]                FRONT = 0, REAR = 1
INSERT_FRONT(5):      OVERFLOW (FRONT already at 0)
DELETE_FRONT():       [20]                    FRONT = 1, REAR = 1
DELETE_REAR():        []                      FRONT = -1, REAR = -1

After INSERT_FRONT(10): FRONT = 0, REAR = 0

After INSERT_REAR(20): FRONT = 0, REAR = 1

INSERT_FRONT(5) fails: FRONT is already at index 0, there's no earlier index to shift into, so this reports OVERFLOW even though the deque still has two empty slots at the rear.

After DELETE_FRONT(): FRONT = 1, REAR = 1

After DELETE_REAR(): FRONT = -1, REAR = -1 (empty again)

Deque complexity

Like a stack and a queue, every core deque operation only touches one of the two ends, so each runs in constant time:

Applications

• Undo/redo with a history limit: a deque of recent actions lets you add and remove from either end, trimming old history off the back while adding new actions to the front.
• Sliding window algorithms: problems like finding the maximum in every window of size k use a deque to efficiently add/remove elements from both ends as the window slides.
• Task scheduling with priorities: some scheduling schemes let high-priority tasks jump to the front while normal tasks queue at the rear, needing insertion at both ends.

Quick recall

• A deque allows insertion and deletion at both the front and the rear, generalizing both stack (LIFO at one end) and queue (FIFO) behavior.
• Input-restricted deques allow insertion at one end only; output-restricted deques allow deletion at one end only; a general deque restricts neither.
• INSERT_FRONT and INSERT_REAR each check their own end's overflow condition independently, one end having room doesn't mean the other does.
• DELETE_FRONT and DELETE_REAR both reset FRONT and REAR to -1 when removing the last remaining element.