Deque — Data Structures -

What is a Deque?

The word Deque stands for Double-Ended Queue.
As the name says, it’s a queue where you can add or remove elements from both ends — the front and the rear.

In a normal queue, we can:

Insert (enqueue) only from the rear
Delete (dequeue) only from the front

But in a deque, we can do both operations from either side.
It’s like having a queue that’s open at both ends!

🎯 Real-Life Analogy

Imagine a line of people waiting to get into a movie theater.
In a normal queue, new people join from the back, and people enter the theater from the front.

Now imagine a special line where people can enter or leave from both ends — maybe there are two doors.
That’s what a deque is!

⚙️ Basic Structure of a Deque

A deque can be visualized as a row of boxes (like memory slots).
You can insert or remove data from the left (front) or the right (rear).

Here’s a simple diagram:

 FRONT                                 REAR
   ↓                                     ↓
+-----+-----+-----+-----+-----+
|     | 10  | 20  | 30  |     |
+-----+-----+-----+-----+-----+
   ↑                       ↑
Insert/Delete         Insert/Delete

So you have four possible operations:

Insert Front – Add an element at the front
Insert Rear – Add an element at the rear
Delete Front – Remove an element from the front
Delete Rear – Remove an element from the rear

🧩 Types of Deques

There are two main types of deques depending on how we allow insertions and deletions:

🔹 1. Input-Restricted Deque

Insertion is allowed only at one end (say, rear)
Deletion is allowed at both ends

✅ Example:
You can only add new people at the back of the line,
but you can remove them either from the front or back.

🔹 2. Output-Restricted Deque

Insertion is allowed at both ends
Deletion is allowed only at one end (say, front)

✅ Example:
People can enter the line from either door,
but they can leave only through one exit.

🧮 Example of Deque Operations

Let’s understand how elements move in a deque step by step.

Step 1: Start Empty

[   ]  [   ]  [   ]  [   ]

Step 2: Insert 10 at Rear

[10]  [   ]  [   ]  [   ]

Step 3: Insert 20 at Rear

[10]  [20]  [   ]  [   ]

Step 4: Insert 5 at Front

[5]  [10]  [20]  [   ]

Step 5: Delete from Rear

[5]  [10]  [   ]  [   ]

So, elements can freely move in and out from both directions.

🧱 Diagram of Deque Operations

Here’s a simple text-based visualization:

Insert Front  → ←  Delete Front
+--------------------------------+
|  5  | 10 | 20 | 30 | 40 |
+--------------------------------+
↑                               ↑
Delete Rear           Insert Rear

You can see both ends are active — this is what makes the deque double-ended.

💡 Why Use a Deque?

Deques are more flexible than simple queues or stacks.
They can act as:

A queue (insert at rear, delete at front)
A stack (insert and delete from the same end)
Or something in between, depending on what you need.

They are especially useful when you need both LIFO (Last In, First Out) and FIFO (First In, First Out) behaviors in the same program.

⚙️ Common Implementations

Deques can be implemented in several ways:

Method	Description
Array-based Deque	Uses a fixed-size array. Simple but has limited capacity.
Linked List-based Deque	Uses nodes linked to each other. Size is dynamic and flexible.
Circular Array	Common in real systems; wraps around the ends to reuse space efficiently.

🧠 Example in Pseudocode

Here’s a small example of how a deque might work:

insertFront(x):
    if deque is full:
        print "Overflow"
    else:
        front = (front - 1 + size) % size
        deque[front] = x

insertRear(x):
    if deque is full:
        print "Overflow"
    else:
        rear = (rear + 1) % size
        deque[rear] = x

deleteFront():
    if deque is empty:
        print "Underflow"
    else:
        front = (front + 1) % size

deleteRear():
    if deque is empty:
        print "Underflow"
    else:
        rear = (rear - 1 + size) % size

🌍 Real-Life Applications

You might not realize it, but deques are everywhere in computer systems:

🧮 Job Scheduling: Tasks can be added or removed from either end based on priority.
🔁 Undo/Redo Feature: Recent actions are added or removed from both ends.
🖼 Browser History: Navigate forward and backward easily.
🧭 Palindrome Checking: Compare characters from both ends of a string.

🧭 Summary

Operation	Front	Rear
Insert Front	✅	❌ or ✅
Delete Front	✅	❌ or ✅
Insert Rear	✅	✅
Delete Rear	✅	✅

A Deque is like a queue, but smarter — you can work from both sides.
It combines the power of stacks and queues in one structure.
Depending on your needs, it can be input-restricted or output-restricted.
It’s widely used in programming, operating systems, and algorithms.