What is a Deque? Double-Ended Queue Explained — GCSE Computer Science

How does a deque differ from a queue and a stack?

A deque is more powerful than either a stack or a queue. A queue can be thought of as a deque restricted to adding only at the rear and removing only at the front. A stack can be thought of as a deque restricted to both adding and removing only at one end.

What are the four core deque operations?

A deque supports four fundamental operations:

• addFront(item) — insert an item at the front of the deque.
• addRear(item) — insert an item at the rear of the deque.
• removeFront() — remove and return the item at the front.
• removeRear() — remove and return the item at the rear.

Additional utility operations:

• peekFront() — examine the front item without removing it.
• peekRear() — examine the rear item without removing it.
• isEmpty() — return True if the deque contains no items.
• size() — return the number of items in the deque.

How is a deque represented and how do the operations work?

Imagine the deque as a horizontal row of numbered boxes: the front is on the left, the rear is on the right.

Front                 Rear
  ←                    →
[10] [20] [30] [40] [50]

• addFront(5) → [5] [10] [20] [30] [40] [50]
• addRear(60) → [5] [10] [20] [30] [40] [50] [60]
• removeFront() → returns 5, deque is [10] [20] [30] [40] [50] [60]
• removeRear() → returns 60, deque is [10] [20] [30] [40] [50]

All four operations are O(1) when implemented with a doubly linked list — no shifting of elements is required because both ends are directly accessible.

How do you use Python's deque from the collections module?

Python's standard library provides an efficient, ready-made deque in the collections module:

from collections import deque

dq = deque([10, 20, 30])

dq.appendleft(5)    # addFront — dq = deque([5, 10, 20, 30])
dq.append(40)       # addRear  — dq = deque([5, 10, 20, 30, 40])
front = dq.popleft()# removeFront — returns 5
rear  = dq.pop()    # removeRear  — returns 40

print(dq)           # deque([10, 20, 30])
print(len(dq))      # 3
print(dq[0])        # 10 (peek front — no removal)
print(dq[-1])       # 30 (peek rear)

collections.deque is implemented as a doubly linked list under the hood, making both appendleft/popleft and append/pop O(1) operations — much faster than using a Python list for front insertions, which are O(n).

What are real-world uses of a deque?

• Browser history — the back/forward stack of visited pages can be implemented as a deque. New pages are added to the rear; pressing Back pops from the rear; pressing Forward is effectively a second deque.
• Undo/redo functionality — actions added to the rear; Undo pops from the rear; Redo moves items back.
• Sliding window algorithms — some algorithms maintain a window of the most recent k values; a deque with a size limit efficiently tracks the window.
• Task scheduling — some schedulers allow high-priority tasks to be added to the front of the queue while normal tasks are added to the rear.

How do you implement a deque in pseudocode?

At GCSE, you may need to describe a deque using an array and two index pointers — front and rear:

front ← 0
rear  ← -1
DECLARE deque[MAX_SIZE]

PROCEDURE addRear(item)
    rear ← rear + 1
    deque[rear] ← item
END PROCEDURE

PROCEDURE removeFront()
    item ← deque[front]
    front ← front + 1
    RETURN item
END PROCEDURE

A circular array implementation prevents wasted space at the front as items are removed.

Frequently asked questions

Is a deque a stack or a queue?

Neither specifically — a deque generalises both. If you use only addRear and removeFront, it behaves exactly like a queue (FIFO). If you use only addRear and removeRear, it behaves exactly like a stack (LIFO). The deque is therefore a more flexible abstract data type that can model either, depending on which operations you restrict yourself to.

What is the difference between collections.deque and a Python list?

Both can hold an ordered sequence and support indexing, but their performance profiles differ. For a Python list, inserting or removing at index 0 (the front) is O(n) because all elements must shift. collections.deque uses a doubly linked list under the hood, making front and rear insertions and deletions O(1). For large datasets that frequently modify the front, deque is significantly faster.

How is a deque different from a priority queue?

A priority queue orders its elements by priority value — the highest-priority element is always removed first, regardless of when it was added. A deque maintains insertion order and gives the programmer explicit control over which end to access. Priority is not a concept in a deque; position (front or rear) is the only organising principle.

Do I need to know deques for the GCSE exam?

AQA and OCR GCSE Computer Science specifications cover stacks, queues, and other abstract data types. The deque is a natural extension that bridges the two, and it may appear in questions asking you to evaluate which data structure is most appropriate for a given scenario. Understanding that a deque gives O(1) front and rear access — and explaining why that is useful — is the level of knowledge expected.

---

For Socratic GCSE tutoring and free Computer Science flashcards, see aitutors.me.