👁 Preview — Study, Practice and Revise are open; mock tests and the rest of the syllabus unlock on subscription. Unlock all · ₹4,999
← Back to Linear Data Structures
Study mode

Deques

Study Practice Revise 🔒 Test

Introduction to Deques in Linear Data Structures

In the study of data structures, linear data structures are those where elements are arranged sequentially, one after another. Common examples include arrays, linked lists, stacks, and queues. Each of these structures has specific rules about how elements are added or removed.

A deque (pronounced "deck") stands for double-ended queue. It is a special linear data structure that allows insertion and deletion of elements from both ends - the front and the rear. This flexibility makes deques more versatile than stacks or queues, which restrict operations to one end only.

Why are deques important? Because many real-world problems require this dual-end access. For example, in task scheduling, sometimes you need to add urgent tasks at the front while normal tasks go to the rear. Deques efficiently support such operations without the overhead of shifting elements, making them essential in competitive programming and system design.

Definition and Types of Deques

A deque is a linear collection of elements that supports insertion and deletion at both its front and rear ends.

Before we dive deeper, let's clarify some terms:

  • Front: The end of the deque where elements can be inserted or removed from the beginning.
  • Rear: The end of the deque where elements can be inserted or removed from the end.
  • Enqueue: The operation of inserting an element.
  • Dequeue: The operation of removing an element.

There are two main types of deques based on restrictions on insertion or deletion:

  • Input-Restricted Deque: Insertion is allowed at only one end (usually rear), but deletion can happen at both ends.
  • Output-Restricted Deque: Deletion is allowed at only one end (usually front), but insertion can happen at both ends.

In a general deque, both insertion and deletion are allowed at both ends.

Front Rear Insert Front Insert Rear Delete Front Delete Rear

Implementation of Deques

Deques can be implemented primarily in two ways:

  • Using Arrays
  • Using Linked Lists

Additionally, a circular array implementation is often used to optimize space and avoid shifting elements.

Aspect Array-based Deque Linked List-based Deque
Memory Usage Fixed size (static), may waste space if not full Dynamic size, uses extra memory for pointers
Insertion/Deletion Time O(1) amortized with circular array; otherwise shifting causes O(n) O(1) guaranteed at both ends
Complexity of Implementation Moderate; requires careful handling of front/rear indices Relatively simple; pointers manage ends
Space Efficiency May be inefficient if size is overestimated Efficient; grows as needed
Wrap-around Handling Needed in circular array implementation Not required

Deque Operations

Let's explore the core operations of a deque. Each operation must handle special cases such as when the deque is empty or full.

graph TD    Start[Start Operation] --> CheckFull{Is Deque Full?}    CheckFull -- Yes --> Overflow[Overflow Error]    CheckFull -- No --> ChooseOp{Insert or Delete?}    ChooseOp -- Insert --> ChooseEndInsert{Insert at Front or Rear?}    ChooseEndInsert -- Front --> InsertFront[Insert Element at Front]    ChooseEndInsert -- Rear --> InsertRear[Insert Element at Rear]    ChooseOp -- Delete --> ChooseEndDelete{Delete from Front or Rear?}    ChooseEndDelete -- Front --> DeleteFront[Delete Element from Front]    ChooseEndDelete -- Rear --> DeleteRear[Delete Element from Rear]    InsertFront --> End[End Operation]    InsertRear --> End    DeleteFront --> CheckEmpty{Is Deque Empty?}    DeleteRear --> CheckEmpty    CheckEmpty -- Yes --> Underflow[Underflow Error]    CheckEmpty -- No --> End

Insertion at Front: Decrement the front pointer and place the new element there.

Insertion at Rear: Increment the rear pointer and place the new element there.

Deletion at Front: Remove the element at the front pointer and increment the front pointer.

Deletion at Rear: Remove the element at the rear pointer and decrement the rear pointer.

In circular array implementations, the front and rear pointers wrap around using modulo arithmetic to stay within array bounds.

Worked Examples

Example 1: Basic Deque Operations Easy
Consider an empty deque implemented using an array of size 5. Perform the following operations in order:
  1. Insert 10 at rear
  2. Insert 20 at front
  3. Insert 30 at rear
  4. Delete element from front
  5. Insert 40 at front
  6. Delete element from rear
Show the contents of the deque after each operation.

Step 1: Insert 10 at rear. Deque: [10]

Step 2: Insert 20 at front. Deque: [20, 10]

Step 3: Insert 30 at rear. Deque: [20, 10, 30]

Step 4: Delete from front removes 20. Deque: [10, 30]

Step 5: Insert 40 at front. Deque: [40, 10, 30]

Step 6: Delete from rear removes 30. Deque: [40, 10]

Answer: Final deque contents are 40 at front and 10 at rear.

Example 2: Circular Array Deque Implementation Medium
A deque is implemented using a circular array of size 5. Initially, front = -1 and rear = -1 (empty). Perform these operations:
  1. Insert 5 at rear
  2. Insert 10 at rear
  3. Insert 15 at rear
  4. Insert 20 at front
  5. Insert 25 at front
  6. Delete from rear
  7. Insert 30 at rear
Show the values of front and rear pointers after each operation and the deque contents.

Step 1: Insert 5 at rear. front=0, rear=0. Deque: [5]

Step 2: Insert 10 at rear. rear=1. Deque: [5, 10]

Step 3: Insert 15 at rear. rear=2. Deque: [5, 10, 15]

Step 4: Insert 20 at front. front moves from 0 to 4 (wrap-around). Deque: [20, 5, 10, 15]

Step 5: Insert 25 at front. front moves from 4 to 3. Deque: [25, 20, 5, 10, 15]

Step 6: Delete from rear. rear moves from 2 to 1. Deque: [25, 20, 5, 10]

Step 7: Insert 30 at rear. rear moves from 1 to 2. Deque: [25, 20, 5, 10, 30]

Answer: The circular nature allows front and rear to wrap around the array efficiently.

Example 3: Using Deque to Check Palindromes Medium
Given the string "RADAR", use a deque to check if it is a palindrome. Describe the steps.

Step 1: Insert all characters into the deque from left to right: R, A, D, A, R.

Step 2: Compare characters from front and rear:

  • Front = 'R', Rear = 'R' -> match, remove both.
  • Front = 'A', Rear = 'A' -> match, remove both.
  • Front = 'D', Rear = 'D' (only one element left) -> palindrome confirmed.

Answer: The string "RADAR" is a palindrome.

Example 4: Sliding Window Maximum Problem Hard
Given an array [2, 1, 3, 4, 6, 3, 8, 9, 10, 12, 56] and window size k = 4, find the maximum in each sliding window using a deque.

Step 1: Initialize an empty deque to store indices.

Step 2: Process first k elements (0 to 3):

  • Index 0 (2): deque empty, add 0.
  • Index 1 (1): 1 < 2, add 1.
  • Index 2 (3): 3 > 1 and 2, remove indices 1 and 0, add 2.
  • Index 3 (4): 4 > 3, remove 2, add 3.

Step 3: For each element from index 4 to end, do:

  • Remove indices outside the current window.
  • Remove smaller elements from rear.
  • Add current index.
  • Maximum is at front of deque.

Step 4: The maximums for windows are: 4, 6, 6, 8, 9, 10, 12, 56.

Answer: Using deque reduces time complexity to O(n) compared to O(nk) in naive methods.

Example 5: Task Scheduling with Deque Hard
Consider a task scheduler where urgent tasks are added to the front of the deque and normal tasks to the rear. Tasks are processed from the front. Given the sequence:
  1. Add normal task T1
  2. Add urgent task T2
  3. Add normal task T3
  4. Process a task
  5. Add urgent task T4
  6. Process two tasks
Show the state of the deque after each step.

Step 1: Add T1 at rear. Deque: [T1]

Step 2: Add T2 at front. Deque: [T2, T1]

Step 3: Add T3 at rear. Deque: [T2, T1, T3]

Step 4: Process task from front (remove T2). Deque: [T1, T3]

Step 5: Add T4 at front. Deque: [T4, T1, T3]

Step 6: Process two tasks from front (remove T4 and T1). Deque: [T3]

Answer: The deque efficiently manages urgent and normal tasks with front and rear operations.

Tips & Tricks

Tip: Remember that deques allow insertion and deletion at both ends, unlike stacks or queues which restrict operations to one end.

When to use: When deciding which linear data structure to use for problems requiring flexible insertion/deletion.

Tip: Use circular array implementation to optimize space and avoid shifting elements during insertions/deletions.

When to use: When implementing deques in memory-constrained environments or for performance-critical applications.

Tip: Visualize front and rear pointers moving in a circular manner to avoid confusion during wrap-around operations.

When to use: While solving problems involving circular deque implementations.

Tip: For palindrome checking, use deque to compare characters from front and rear without extra space.

When to use: When asked to check palindromes efficiently in string processing problems.

Tip: In sliding window problems, maintain a deque of indices to track maximum or minimum elements efficiently.

When to use: When solving range query problems in arrays or sequences.

Common Mistakes to Avoid

❌ Confusing the front and rear ends during insertion or deletion operations.
✓ Always clearly define and track which end is front and which is rear; use diagrams to visualize.
Why: Because both ends can be used in deques, students often mix up operations leading to incorrect results.
❌ Not handling wrap-around conditions properly in circular array implementations.
✓ Use modulo arithmetic to update front and rear pointers to stay within array bounds.
Why: Students forget to apply modulo, causing index out-of-bound errors or overwriting data.
❌ Assuming deque operations have the same time complexity as linked lists without considering implementation details.
✓ Clarify that array-based deques can have O(1) amortized time with circular arrays, while linked lists have O(1) guaranteed time.
Why: Misunderstanding implementation leads to incorrect complexity analysis.
❌ Using deque when a simpler stack or queue would suffice, leading to unnecessary complexity.
✓ Analyze problem requirements carefully to choose the simplest data structure that fits.
Why: Overcomplicating solutions wastes time and may confuse examiners.
❌ Forgetting to check for empty or full conditions before performing insertions or deletions.
✓ Always include boundary condition checks to avoid runtime errors.
Why: Neglecting these checks causes runtime exceptions or logical errors.

Deque vs Stack vs Queue

FeatureDequeStackQueue
InsertionFront & RearTop onlyRear only
DeletionFront & RearTop onlyFront only
FlexibilityHighLowMedium
Use Cases YesFunction calls, undo operationsOrder processing, buffering

Key Takeaways on Deques

  • Deques allow insertion and deletion at both ends, unlike stacks and queues.
  • Two main types: input-restricted and output-restricted deques.
  • Implemented using arrays (circular) or linked lists.
  • Efficient operations with O(1) time complexity.
  • Useful in palindrome checking, sliding window problems, and task scheduling.
Key Takeaway:

Understanding deques enhances problem-solving flexibility in competitive exams.

Curated videos per subtopic
Top YouTube explainers, AI-ranked for your exam and language. Unlocks with subscription.
Unlock

Try Practice next.

Progress tracking is paywalled — subscribe to mark subtopics as understood and save your streak.

Go to practice →
Ask a doubt
Deques · 10 free messages
Ask me anything about this subtopic. You have 10 free messages this session — chat history isn't saved in preview.