Dequeue Operation in DSA C++

Mental Model

A dequeue lets you add or remove items from both ends, like a line where people can enter or leave from front or back.

Analogy: Imagine a double-ended queue as a hallway where people can enter or exit from either door at the front or the back.

front -> [1] -> [2] -> [3] -> back
↑front pointer          ↑back pointer

Dry Run Walkthrough

Input: dequeue: 1 -> 2 -> 3, perform dequeue operation from front and then from back

Goal: Remove one element from the front and one from the back, showing how the structure updates

Step 1: Remove element 1 from the front

front -> [2] -> [3] -> back
↑front pointer          ↑back pointer

Why: Removing from front updates front pointer to next element

Step 2: Remove element 3 from the back

front -> [2] -> back
↑front pointer  ↑back pointer

Why: Removing from back updates back pointer to previous element

Result:

front -> [2] -> back
↑front pointer  ↑back pointer

Annotated Code

DSA C++

#include <iostream>
using namespace std;

class Dequeue {
private:
    int arr[100];
    int front, back, size;
public:
    Dequeue() {
        front = -1;
        back = -1;
        size = 100;
    }

    bool isEmpty() {
        return front == -1;
    }

    bool isFull() {
        return (front == 0 && back == size - 1) || (front == back + 1);
    }

    void insertBack(int val) {
        if (isFull()) {
            cout << "Dequeue is full\n";
            return;
        }
        if (isEmpty()) {
            front = back = 0;
        } else if (back == size - 1) {
            back = 0;
        } else {
            back++;
        }
        arr[back] = val;
    }

    void insertFront(int val) {
        if (isFull()) {
            cout << "Dequeue is full\n";
            return;
        }
        if (isEmpty()) {
            front = back = 0;
        } else if (front == 0) {
            front = size - 1;
        } else {
            front--;
        }
        arr[front] = val;
    }

    void deleteFront() {
        if (isEmpty()) {
            cout << "Dequeue is empty\n";
            return;
        }
        if (front == back) {
            front = back = -1;
        } else if (front == size - 1) {
            front = 0;
        } else {
            front++;
        }
    }

    void deleteBack() {
        if (isEmpty()) {
            cout << "Dequeue is empty\n";
            return;
        }
        if (front == back) {
            front = back = -1;
        } else if (back == 0) {
            back = size - 1;
        } else {
            back--;
        }
    }

    void display() {
        if (isEmpty()) {
            cout << "Dequeue is empty\n";
            return;
        }
        int i = front;
        while (true) {
            cout << arr[i];
            if (i == back) break;
            cout << " -> ";
            i = (i + 1) % size;
        }
        cout << " -> null\n";
    }
};

int main() {
    Dequeue dq;
    dq.insertBack(1);
    dq.insertBack(2);
    dq.insertBack(3);
    dq.display();
    dq.deleteFront();
    dq.display();
    dq.deleteBack();
    dq.display();
    return 0;
}

if (isEmpty()) { front = back = 0; } else if (back == size - 1) { back = 0; } else { back++; }

advance back pointer circularly to insert at back

if (isEmpty()) { front = back = 0; } else if (front == 0) { front = size - 1; } else { front--; }

move front pointer circularly to insert at front

if (front == back) { front = back = -1; } else if (front == size - 1) { front = 0; } else { front++; }

advance front pointer circularly to delete from front

if (front == back) { front = back = -1; } else if (back == 0) { back = size - 1; } else { back--; }

move back pointer circularly to delete from back

while (true) { cout << arr[i]; if (i == back) break; cout << " -> "; i = (i + 1) % size; }

iterate from front to back circularly to display elements

Output

1 -> 2 -> 3 -> null

2 -> 3 -> null

2 -> null

Complexity Analysis

Time: O(1) for each dequeue operation because pointers move without traversing all elements

Space: O(n) because the dequeue stores up to n elements in an array

vs Alternative: Compared to a simple queue that only removes from front, dequeue allows removal from both ends with same O(1) cost

Edge Cases

empty dequeue

delete operations print 'Dequeue is empty' and do nothing

DSA C++

if (isEmpty()) { cout << "Dequeue is empty\n"; return; }

single element dequeue

deleting front or back resets pointers to -1 indicating empty

DSA C++

if (front == back) { front = back = -1; }

circular wrap around

front or back pointers wrap around array ends correctly

DSA C++

else if (front == size - 1) { front = 0; } and else if (back == 0) { back = size - 1; }

When to Use This Pattern

When you need to add or remove items from both ends of a list efficiently, use the dequeue pattern because it supports double-ended operations in constant time.

Common Mistakes

Mistake: Not updating front or back pointers correctly when deleting from empty or single-element dequeue
Fix: Check if dequeue is empty before deleting and reset pointers to -1 when last element is removed

Mistake: Not handling circular wrap around causing index out of bounds
Fix: Use modulo or conditional checks to wrap front and back pointers within array bounds

Summary

It removes elements from either the front or back of a dequeue.

Use it when you want flexible removal from both ends of a list.

The key is to move front and back pointers carefully and wrap around the array.

Practice

1. What is the main difference between a deque and a regular queue in data structures?

easy

A. Deque allows insertion and deletion from both ends, queue only from front and rear respectively

B. Deque only allows insertion at the rear, queue allows insertion at both ends

C. Deque is always sorted, queue is not

D. Deque uses arrays, queue uses linked lists

Solution

1. Step 1: Understand queue operations

   A regular queue allows insertion at the rear and deletion from the front only.

2. Step 2: Understand deque operations

   A deque (double-ended queue) allows insertion and deletion at both front and rear ends.

3. Final Answer:

   Deque allows insertion and deletion from both ends, queue only from front and rear respectively -> Option A

4. Quick Check:

   Deque = double-ended queue [OK]

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

Common Mistakes:

• Thinking deque only inserts at rear
• Confusing deque with sorted data structure
• Assuming deque uses only arrays

2. Which of the following is the correct syntax to insert an element 10 at the front of a std::deque<int> named d in C++?

easy

A. d.push(10);

B. d.push_front(10);

C. d.insert_front(10);

D. d.add_front(10);

Solution

1. Step 1: Recall deque insertion methods

   In C++, std::deque uses push_front() to insert at the front.

2. Step 2: Check method names

   Only push_front(10); is valid syntax for front insertion.

3. Final Answer:

   d.push_front(10); -> Option B

4. Quick Check:

   push_front() inserts at front [OK]

Hint: Use push_front() to add at front in deque [OK]

Common Mistakes:

• Using push() which is not a deque method
• Using insert_front() which doesn't exist
• Confusing with vector methods

3. What will be the output of the following C++ code snippet?

std::deque<int> d = {1, 2, 3};
d.push_front(0);
d.push_back(4);
d.pop_front();
for (int x : d) std::cout << x << " ";

medium

A. 1 2 3 4

B. 0 1 2 3 4

C. 1 2 3

D. 0 1 2 3

Solution

1. Step 1: Trace deque operations

   Initial deque: [1, 2, 3]
   After push_front(0): [0, 1, 2, 3]
   After push_back(4): [0, 1, 2, 3, 4]
   After pop_front(): removes 0, deque becomes [1, 2, 3, 4]

2. Step 2: Print elements

   Elements printed are 1 2 3 4 with spaces.

3. Final Answer:

   1 2 3 4 -> Option A

4. Quick Check:

   pop_front removes first element [OK]

Hint: pop_front removes first inserted element [OK]

Common Mistakes:

• Forgetting pop_front removes 0
• Confusing push_front and push_back order
• Printing without spaces

4. Identify the error in the following C++ code using std::deque:

std::deque<int> d;
d.push_back(5);
d.pop_front();
std::cout << d.front();

medium

A. deque must be initialized with size

B. push_back() syntax is incorrect

C. pop_front() called on empty deque causes undefined behavior

D. front() cannot be used after pop_front()

Solution

1. Step 1: Analyze deque state after operations

   Initially, deque is empty.
   push_back(5) adds 5: deque = [5]
   pop_front() removes 5: deque becomes empty again.

2. Step 2: Check front() usage

   Calling front() on empty deque is undefined behavior and may cause runtime error.

3. Final Answer:

   pop_front() called on empty deque causes undefined behavior -> Option C

4. Quick Check:

   front() on empty deque is invalid [OK]

Hint: Don't pop from empty deque before accessing front [OK]

Common Mistakes:

• Assuming front() returns 5 after pop_front
• Thinking push_back syntax is wrong
• Believing deque needs size at initialization

5. Given a std::deque<int> d = {10, 20, 30, 40, 50}, which sequence of operations will result in the deque containing 10 20 30 after all operations?

hard

A. d.pop_back(); d.pop_front();

B. d.pop_front(); d.pop_back();

C. d.pop_front(); d.pop_front();

D. d.pop_back(); d.pop_back();

Solution

1. Step 1: Start with initial deque

   Deque = [10, 20, 30, 40, 50]

2. Step 2: Apply operations for each option

   d.pop_back(); d.pop_back();: pop_back() removes 50 -> [10, 20, 30, 40], pop_back() removes 40 -> [10, 20, 30]
   d.pop_front(); d.pop_back();: pop_front() removes 10 -> [20, 30, 40, 50], pop_back() removes 50 -> [20, 30, 40]
   d.pop_front(); d.pop_front();: pop_front() twice removes 10 and 20 -> [30, 40, 50]
   d.pop_back(); d.pop_front();: pop_back() removes 50 -> [10, 20, 30, 40], pop_front() removes 10 -> [20, 30, 40]

3. Step 3: Compare results

   Only d.pop_back(); d.pop_back(); results in [10, 20, 30]. The other sequences result in different contents.

4. Final Answer:

   d.pop_back(); d.pop_back(); -> Option D

5. Quick Check:

   Two pop_back() removes the last two elements [OK]

Hint: pop_back twice removes last two elements [OK]

Common Mistakes:

• Removing wrong ends in wrong order
• Assuming pop_back twice keeps 20
• Confusing pop_front and pop_back effects