Module 5 · Interactive topic

Double-Ended Queue

Insert and delete at BOTH ends

A deque (say “deck”) is a queue that works from both ends: you can insert at the front or the rear, and delete from the front or the rear. It is stored in a circular array, so both front and rear wrap around. Try the two restricted forms too: an input-restricted deque inserts at one end only, an output-restricted deque deletes at one end only.

  • Frontinsert or delete here
  • Rearinsert or delete here too
  • Wrap-aroundfront − 1 and rear + 1, % N
  • Restrictedinput- or output-restricted
Deque Ready
size 3 / 8
front 0
rear 2
status OK
As an array
  • Current
  • New / found
  • Leaving
  • Empty
↻clockwise
front
rear

Ready

Comparisons 0 Shifts 0
Ready

Keyboard: ← → step · Space play / pause · R reset · Esc exit classroom mode

How it works

Every operation, in plain steps

These are exactly the steps the visualizer animates.

A circular array with two moving ends

A deque is stored like a circular queue: an array of N slots and two indexes, front and rear (both −1 when it is empty). The difference is that BOTH ends move in BOTH directions. Inserting at the rear moves rear forward, inserting at the front moves front backward; deleting at the front moves front forward, deleting at the rear moves rear backward. Every step wraps around with % N.

#define N 8

int dq[N];
int front = -1, rear = -1;     // -1 means empty

// one step forward:  i = (i + 1) % N
// one step back:     i = (i - 1 + N) % N     // the + N keeps it from going negative

Insert Rear

  1. Check the deque is not full.
  2. If it is empty: front = rear = 0.
  3. Otherwise rear = (rear + 1) % N.
  4. Store the value at dq[rear].

Insert Front

  1. Check the deque is not full.
  2. If it is empty: front = rear = 0.
  3. Otherwise front = (front − 1 + N) % N: one step BACK.
  4. Store the value at dq[front].

Delete Front

  1. Check the deque is not empty.
  2. Take x = dq[front].
  3. If front == rear it was the last item: front = rear = −1.
  4. Otherwise front = (front + 1) % N.

Delete Rear

  1. Check the deque is not empty.
  2. Take x = dq[rear].
  3. If front == rear it was the last item: front = rear = −1.
  4. Otherwise rear = (rear − 1 + N) % N: one step BACK.

Peek, Is Empty, Is Full

  1. Peek Front returns dq[front]; Peek Rear returns dq[rear].
  2. Is Empty: front == −1.
  3. Is Full: (rear + 1) % N == front.
  4. None of them changes the deque.

Wrap-around

  1. Stepping back from index 0 lands on N − 1.
  2. Stepping on from index N − 1 lands on 0.
  3. The + N in (i − 1 + N) % N avoids a negative index.
  4. So no slot is ever wasted.

Input-restricted deque

  1. Insert at ONE end only: the rear.
  2. Delete at both ends.
  3. Insert Front is not allowed.
  4. Useful when you control what goes in but may remove from either side.

Output-restricted deque

  1. Delete at ONE end only: the front.
  2. Insert at both ends.
  3. Delete Rear is not allowed.
  4. Useful when items arrive from either side but must leave in one order.

Where deques are used

  1. Undo history: new actions at one end, the oldest dropped from the other.
  2. Sliding-window problems (the window's maximum).
  3. Work stealing between processors.
  4. A deque can act as a stack OR as a queue.
Algorithm

Pseudocode

Language-independent steps. The visualizer shows the same logic in C, Python and Java.

1 INSERT-REAR(x)
2 if (rear + 1) mod N = front then overflow
3 if front = −1 then front ← 0 and rear ← 0
4 else rear ← (rear + 1) mod N
5 dq[rear] ← x
Complexity

How fast is each operation?

n = number of items. Every deque operation changes at most two indexes and one slot, so each one takes O(1) time whatever the size. The array needs O(N) space for its N slots.

Operation Best Average Worst Speed
Insert Front / Insert Rear O(1) O(1) O(1) Instant
Delete Front / Delete Rear O(1) O(1) O(1) Instant
Peek Front / Peek Rear O(1) O(1) O(1) Instant
Is Empty / Is Full O(1) O(1) O(1) Instant

Stack, queue and deque

Stack Queue Deque
Insert at the top the rear the front or the rear
Delete from the top the front the front or the rear
Order LIFO FIFO both
Can it replace another? no no yes: a stack or a queue

The three kinds of deque

Kind Insert at Delete from Not allowed
Deque front and rear front and rear nothing
Input-restricted rear only front and rear Insert Front
Output-restricted front and rear front only Delete Rear
Practice

Check your understanding

Answer each question — you will see the explanation straight away.

0 / 7 correct
Question 1

Which deque operation moves front BACKWARD?

Question 2

N = 8 and front = 0. You insert at the front. Where does front go?

Question 3

An INPUT-restricted deque does NOT allow…

Question 4

An OUTPUT-restricted deque does NOT allow…

Question 5

How long does Insert Front take in a circular-array deque?

Question 6

How can you tell that the deque is full?

Question 7

front == rear and you Delete Front. What happens?

Assessment

Queues quiz

Test yourself: 5 questions, 70% to pass. Create a free account to take the quiz, save your progress and work towards the certificate.

Create a free account →
← Previous topic Priority Queue Next topic → Binary Trees