Double Ended Queue Deque in DSA C - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is a Double Ended Queue (Deque)?

A Double Ended Queue, or Deque, is a data structure where elements can be added or removed from both the front and the back ends.

beginner

Name two main operations that can be performed on both ends of a Deque.

Insertion (adding elements) and Deletion (removing elements) can be done at both the front and the rear ends of a Deque.

intermediate

In a Deque, what happens if you try to insert an element when it is full?

If the Deque is full, no more elements can be added until some are removed. This condition is called overflow.

beginner

How is a Deque different from a regular Queue?

A regular Queue allows insertion at the rear and deletion at the front only, while a Deque allows insertion and deletion at both front and rear ends.

intermediate

What is the typical use case for a Deque?

Deques are useful when you need to access or modify elements from both ends efficiently, such as in undo operations, palindromes checking, or sliding window problems.

Which operation is NOT possible in a Deque?

A Delete at rear

B Insert at middle

C Insert at front

D Delete at front

Deques allow insertion and deletion only at the front and rear ends, not in the middle.

What does 'overflow' mean in the context of a Deque?

A Deque is empty

B Deque has duplicate elements

C Deque has one element

D Deque is full

Overflow means the Deque is full and cannot accept new elements.

Which of these is a valid operation on a Deque?

A Insert at front and delete at rear

B Insert at middle

C Delete at middle

D Insert only at rear

Deques support insertion and deletion at both front and rear ends.

If you want to implement undo functionality, which data structure is most suitable?

A Deque

B Queue

C Stack

D Linked List

Deque allows adding and removing from both ends, useful for undo operations.

What is the output after these operations on an empty Deque: insertFront(10), insertRear(20), deleteFront(), insertFront(30)?

A 20 -> 30 -> null

B 10 -> 20 -> null

C 30 -> 20 -> null

D 30 -> 10 -> null

After insertFront(10) and insertRear(20), Deque is 10 -> 20. deleteFront() removes 10, leaving 20. insertFront(30) adds 30 at front, so Deque is 30 -> 20.

Explain how insertion and deletion work in a Double Ended Queue (Deque).

Think about adding or removing elements from both ends.

Describe a real-life example where a Deque would be useful and why.

Consider situations like undo actions or sliding windows.

Practice

1. What is a Double Ended Queue (Deque)?

easy

A. A queue where insertion happens only at the rear and deletion at the front

B. A data structure where insertion and deletion can happen at both ends

C. A stack where insertion and deletion happen only at one end

D. A list that allows random access to elements

Solution

1. Step 1: Understand the definition of Deque

   A Deque allows adding and removing elements from both front and rear ends.

2. Step 2: Compare with other data structures

   Unlike a queue or stack, Deque supports operations at both ends.

3. Final Answer:

   A data structure where insertion and deletion can happen at both ends -> Option B

4. Quick Check:

   Deque = Both ends insertion/deletion [OK]

Hint: Deque means double-ended queue, both ends allowed [OK]

Common Mistakes:

• Confusing deque with stack or queue
• Thinking insertion is only at one end
• Assuming random access like arrays

2. Which of the following is the correct syntax to initialize an empty deque in C using an array implementation?

easy

A. int deque[] = {}; int front = 0, rear = 0;

B. int deque[SIZE] = NULL; int front = 0, rear = 0;

C. int deque[SIZE]; int front = -1, rear = -1;

D. int deque[SIZE]; int front = 0, rear = -1;

Solution

1. Step 1: Understand initialization of deque with front and rear

   Front and rear are set to -1 to indicate empty deque.

2. Step 2: Check array declaration and initial values

   int deque[SIZE]; int front = -1, rear = -1; correctly declares array and sets front and rear to -1.

3. Final Answer:

   int deque[SIZE]; int front = -1, rear = -1; -> Option C

4. Quick Check:

   Empty deque front and rear = -1 [OK]

Hint: Empty deque front and rear start at -1 [OK]

Common Mistakes:

• Setting front or rear to 0 initially
• Using NULL for array initialization
• Leaving array size unspecified

3. Consider the following operations on an empty deque of size 5 implemented using an array:
insertRear(10); insertRear(20); insertFront(5); deleteRear(); insertFront(15);
What is the content of the deque from front to rear after these operations?

medium

A. 15 -> 5 -> 10 -> null

B. 5 -> 15 -> 10 -> null

C. 15 -> 5 -> null

D. 10 -> 5 -> 15 -> null

Solution

1. Step 1: Perform insertRear(10) and insertRear(20)

   Deque: 10 -> 20

2. Step 2: Perform insertFront(5)

   Deque: 5 -> 10 -> 20

3. Step 3: Perform deleteRear()

   Removes 20, Deque: 5 -> 10

4. Step 4: Perform insertFront(15)

   Deque: 15 -> 5 -> 10

5. Final Answer:

   15 -> 5 -> 10 -> null -> Option A

6. Quick Check:

   Operations result in 15,5,10 order [OK]

Hint: Track front and rear insertions stepwise [OK]

Common Mistakes:

• Forgetting deleteRear removes last element
• Mixing order of insertFront and insertRear
• Assuming insertFront adds at rear

4. Given the following code snippet for deque insertion at front, identify the error:

void insertFront(int deque[], int *front, int *rear, int value) {
  if (*front == 0) {
    printf("Deque is full at front\n");
    return;
  }
  (*front)--;
  deque[*front] = value;
}

medium

A. It incorrectly checks full condition only at front == 0

B. It decrements front before insertion causing invalid index

C. It does not check if deque is empty before insertion

D. It should increment front instead of decrement

Solution

1. Step 1: Analyze the full condition check

   Checking only if front == 0 is not enough to detect full deque.

2. Step 2: Understand circular deque logic

   Deque can be full even if front != 0, so this check is incomplete.

3. Final Answer:

   It incorrectly checks full condition only at front == 0 -> Option A

4. Quick Check:

   Full check must consider rear position too [OK]

Hint: Full deque check needs both front and rear positions [OK]

Common Mistakes:

• Assuming front == 0 means full always
• Not handling circular wrap-around
• Decrementing front without boundary check

5. You have a deque of size 4 implemented using a circular array. Initially empty, you perform:
insertRear(1); insertRear(2); insertFront(3); insertFront(4); deleteRear(); insertRear(5);
What is the final state of the deque from front to rear?

hard

A. 4 -> 3 -> 1 -> null

B. 4 -> 3 -> 5 -> null

C. 3 -> 4 -> 1 -> 5 -> null

D. 4 -> 3 -> 1 -> 5 -> null

Solution

1. Step 1: InsertRear(1), InsertRear(2)

   Deque: 1 -> 2

2. Step 2: InsertFront(3), InsertFront(4)

   Deque: 4 -> 3 -> 1 -> 2 (deque full)

3. Step 3: DeleteRear()

   Removes 2, Deque: 4 -> 3 -> 1

4. Step 4: InsertRear(5)

   Deque: 4 -> 3 -> 1 -> 5 (full again)

5. Final Answer:

   4 -> 3 -> 1 -> 5 -> null -> Option D

6. Quick Check:

   Circular deque final state matches 4 -> 3 -> 1 -> 5 -> null [OK]

Hint: Track circular wrap and full capacity carefully [OK]

Common Mistakes:

• Ignoring circular wrap-around
• Misordering front and rear elements
• Forgetting deleteRear removes last element