Dequeue Operation in DSA Java - Build from Scratch

Dequeue Operation

📖 Scenario: Imagine you are managing a line of customers waiting for service. Sometimes customers join the line at the front or the back, and sometimes customers leave from the front or the back. This line is called a deque (double-ended queue).

🎯 Goal: You will create a deque using Java's ArrayDeque, add some customers, remove customers from both ends, and then print the final state of the deque.

📋 What You'll Learn

Create an ArrayDeque of strings called customers with initial customers.

Add a new customer to the front and another to the back of the deque.

Remove one customer from the front and one from the back of the deque.

Print the final state of the deque showing all remaining customers.

💡 Why This Matters

🌍 Real World

Deques are useful in real-world situations like managing lines where people can join or leave from both ends, such as ticket counters or call centers.

💼 Career

Understanding deque operations is important for software roles that involve queue management, scheduling, or real-time data processing.

1

Create the initial deque

Create an ArrayDeque<String> called customers and add these exact customers in order: "Alice", "Bob", "Charlie".

DSA Java

import java.util.ArrayDeque;

public class Main {
    public static void main(String[] args) {
        // Create the ArrayDeque called customers and add Alice, Bob, Charlie
        // Your code here
    }
}

Hint

Use ArrayDeque<String> customers = new ArrayDeque<>(); to create the deque. Then use customers.add() to add each customer.

2

Add customers to front and back

Add a customer named "Diana" to the front of customers using addFirst, and add a customer named "Ethan" to the back using addLast.

DSA Java

import java.util.ArrayDeque;

public class Main {
    public static void main(String[] args) {
        ArrayDeque customers = new ArrayDeque();
        customers.add("Alice");
        customers.add("Bob");
        customers.add("Charlie");
        // Add Diana to the front and Ethan to the back
        // Your code here
    }
}

Hint

Use customers.addFirst("Diana") to add at the front and customers.addLast("Ethan") to add at the back.

3

Remove customers from front and back

Remove one customer from the front of customers using removeFirst and one from the back using removeLast.

DSA Java

import java.util.ArrayDeque;

public class Main {
    public static void main(String[] args) {
        ArrayDeque customers = new ArrayDeque();
        customers.add("Alice");
        customers.add("Bob");
        customers.add("Charlie");
        customers.addFirst("Diana");
        customers.addLast("Ethan");
        // Remove one customer from the front and one from the back
        // Your code here
    }
}

Hint

Use customers.removeFirst() to remove from the front and customers.removeLast() to remove from the back.

4

Print the final deque

Print the final state of customers using System.out.println(customers); to show all remaining customers.

DSA Java

import java.util.ArrayDeque;

public class Main {
    public static void main(String[] args) {
        ArrayDeque customers = new ArrayDeque();
        customers.add("Alice");
        customers.add("Bob");
        customers.add("Charlie");
        customers.addFirst("Diana");
        customers.addLast("Ethan");
        customers.removeFirst();
        customers.removeLast();
        // Print the final deque
        // Your code here
    }
}

Hint

Use System.out.println(customers); to print the deque.

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