Dequeue Operation in DSA Java

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
↑
current front

Dry Run Walkthrough

Input: dequeue with elements 1 -> 2 -> 3, perform removeFront and removeRear

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

Step 1: remove element from front (1)

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

Why: Removing from front updates the front pointer to the next element

Step 2: remove element from rear (3)

front -> [2] -> back
↑
front and rear point to 2

Why: Removing from rear updates the rear pointer to the previous element

Result:

front -> [2] -> back
↑
front and rear point to 2

Annotated Code

DSA Java

class Node {
    int data;
    Node prev, next;
    Node(int data) {
        this.data = data;
        this.prev = null;
        this.next = null;
    }
}

class Dequeue {
    Node front, rear;

    Dequeue() {
        front = null;
        rear = null;
    }

    void addRear(int data) {
        Node newNode = new Node(data);
        if (rear == null) {
            front = rear = newNode;
            return;
        }
        rear.next = newNode; // link new node after rear
        newNode.prev = rear; // link new node back to rear
        rear = newNode;      // update rear to new node
    }

    int removeFront() {
        if (front == null) {
            return -1; // empty dequeue
        }
        int val = front.data;
        front = front.next; // move front forward
        if (front != null) {
            front.prev = null; // detach old front
        } else {
            rear = null; // dequeue is empty now
        }
        return val;
    }

    int removeRear() {
        if (rear == null) {
            return -1; // empty dequeue
        }
        int val = rear.data;
        rear = rear.prev; // move rear backward
        if (rear != null) {
            rear.next = null; // detach old rear
        } else {
            front = null; // dequeue is empty now
        }
        return val;
    }

    void printDequeue() {
        Node curr = front;
        while (curr != null) {
            System.out.print(curr.data);
            if (curr.next != null) {
                System.out.print(" -> ");
            }
            curr = curr.next;
        }
        System.out.println(" -> null");
    }
}

public class Main {
    public static void main(String[] args) {
        Dequeue dq = new Dequeue();
        dq.addRear(1);
        dq.addRear(2);
        dq.addRear(3);
        dq.printDequeue();

        int frontRemoved = dq.removeFront();
        System.out.println("Removed from front: " + frontRemoved);
        dq.printDequeue();

        int rearRemoved = dq.removeRear();
        System.out.println("Removed from rear: " + rearRemoved);
        dq.printDequeue();
    }
}

rear.next = newNode; // link new node after rear

attach new node after current rear to extend dequeue at rear

newNode.prev = rear; // link new node back to rear

link new node back to current rear for double linkage

rear = newNode; // update rear to new node

update rear pointer to new last node

front = front.next; // move front forward

advance front pointer to next node to remove front element

front.prev = null; // detach old front

remove backward link from new front to old front

rear = rear.prev; // move rear backward

move rear pointer backward to remove last element

rear.next = null; // detach old rear

remove forward link from new rear to old rear

Output

1 -> 2 -> 3 -> null

Removed from front: 1

2 -> 3 -> null

Removed from rear: 3

2 -> null

Complexity Analysis

Time: O(1) because adding or removing from front or rear only changes a few pointers without traversal

Space: O(n) because each element is stored in a node with pointers

vs Alternative: Compared to a singly linked list, double linked dequeue allows O(1) removal from both ends, while singly linked list can only remove efficiently from front

Edge Cases

empty dequeue

removeFront or removeRear returns -1 indicating no element to remove

DSA Java

if (front == null) { return -1; }

single element dequeue

removing front or rear empties the dequeue and sets both pointers to null

DSA Java

else { rear = null; } and else { front = null; }

When to Use This Pattern

When you need to add or remove items from both ends efficiently, look for the dequeue operation pattern because it supports O(1) insertions and deletions at front and rear.

Common Mistakes

Mistake: Not updating both front and rear pointers when the dequeue becomes empty after removal
Fix: Set both front and rear to null when the last element is removed

Mistake: Forgetting to detach old nodes by not updating prev or next pointers after removal
Fix: Always set the prev or next pointer of the new front or rear to null after removal

Summary

It removes elements from either the front or rear of a double-ended queue.

Use it when you want fast removal from both ends without traversing the whole structure.

The key is updating pointers carefully to keep the structure connected and avoid dangling links.

Practice

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

easy

A. Deque is slower than queue in all operations

B. Deque only allows insertion, queue only allows deletion

C. Deque allows insertion and deletion from both ends, queue only from one end

D. Deque stores elements in sorted order, queue does not

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 one end -> Option C

4. Quick Check:

   Deque = Both ends operations [OK]

Hint: Deque = double-ended operations, queue = single-ended [OK]

Common Mistakes:

• Thinking deque only allows insertion
• Confusing deque with stack
• Assuming deque stores sorted data

2. Which of the following is the correct way to add an element to the front of a Java Deque named dq?

easy

A. dq.addLast(element);

B. dq.addFirst(element);

C. dq.pushBack(element);

D. dq.enqueueFront(element);

Solution

1. Step 1: Recall Java Deque methods

   Java Deque interface provides addFirst() to add element at the front.

2. Step 2: Check options for correct method

   Only dq.addFirst(element); correctly adds at front.

3. Final Answer:

   dq.addFirst(element); -> Option B

4. Quick Check:

   addFirst() adds front [OK]

Hint: Use addFirst() to add at front in Java Deque [OK]

Common Mistakes:

• Using addLast() to add at front
• Using non-existent methods like pushBack()
• Confusing enqueue with Deque methods

3. What will be the output of the following Java code?

Deque<Integer> dq = new ArrayDeque<>();
dq.addLast(10);
dq.addFirst(20);
dq.addLast(30);
System.out.println(dq);

medium

A. [20, 30, 10]

B. [10, 20, 30]

C. [30, 10, 20]

D. [20, 10, 30]

Solution

1. Step 1: Trace additions to deque

   First addLast(10) adds 10 at rear: [10]. Then addFirst(20) adds 20 at front: [20, 10]. Then addLast(30) adds 30 at rear: [20, 10, 30].

2. Step 2: Print deque state

   Printing dq shows elements in order: [20, 10, 30].

3. Final Answer:

   [20, 10, 30] -> Option D

4. Quick Check:

   addFirst adds front, addLast adds rear [OK]

Hint: Track addFirst at front, addLast at rear [OK]

Common Mistakes:

• Mixing order of addFirst and addLast
• Assuming addLast adds at front
• Confusing printed order with insertion order

4. Identify the error in the following Java code snippet using Deque:

Deque<String> dq = new LinkedList<>();
dq.addFirst("A");
dq.addLast("B");
dq.removeFront();
System.out.println(dq);

medium

A. removeFront() method does not exist in Deque

B. addFirst() cannot be used with LinkedList

C. Deque cannot store String elements

D. dq should be initialized with ArrayDeque, not LinkedList

Solution

1. Step 1: Check Deque methods

   Deque interface does not have a method named removeFront(). The correct method to remove from front is removeFirst().

2. Step 2: Verify other statements

   addFirst() works with LinkedList, Deque can store Strings, and LinkedList is a valid Deque implementation.

3. Final Answer:

   removeFront() method does not exist in Deque -> Option A

4. Quick Check:

   Use removeFirst() to remove front [OK]

Hint: Use removeFirst(), not removeFront() [OK]

Common Mistakes:

• Using removeFront() instead of removeFirst()
• Thinking LinkedList can't implement Deque
• Confusing method names for removal

5. Given a Deque dq initially empty, which sequence of operations will result in the deque containing [5, 10, 15] from front to rear?

hard

A. dq.addFirst(5); dq.addLast(10); dq.addLast(15);

B. dq.addLast(15); dq.addLast(10); dq.addLast(5);

C. dq.addFirst(5); dq.addFirst(10); dq.addFirst(15);

D. dq.addLast(5); dq.addLast(15); dq.addLast(10);

Solution

1. Step 1: Analyze dq.addFirst(5); dq.addLast(10); dq.addLast(15); operations

   Start empty: []. addFirst(5) -> [5]. addLast(10) -> [5, 10]. addLast(15) -> [5, 10, 15].

2. Step 2: Verify final deque order

   Deque after operations is [5, 10, 15], matching the required order.

3. Final Answer:

   dq.addFirst(5); dq.addLast(10); dq.addLast(15); -> Option A

4. Quick Check:

   addFirst front, addLast rear = correct order [OK]

Hint: Add 5 front, then 10 and 15 at rear for correct order [OK]

Common Mistakes:

• Adding all elements at front reverses order
• Adding all elements at rear but starting with wrong element
• Mixing addFirst and addLast order