Deque (Double Ended Queue)

# CHAPTER 14

Deque (Double Ended Queue) #

1. Introduction #

2. Learning Objectives #

• Define the structural freedoms of a Deque.

• Execute the four distinct Deque operations.

• Understand how Doubly Linked Lists power the ideal Deque implementation.

• Identify scenarios where a Deque outperforms standard Stacks or Queues.

3. The Four Core Operations #

1. 1. insertFront(data): Injects data directly to the Head.

1. 2. insertRear(data): Appends data to the Tail. (Standard Queue behavior).

1. 3. deleteFront(): Removes data from the Head. (Standard Queue behavior).

1. 4. deleteRear(): Removes data from the Tail.

4. Implementation Strategy #

• Using an Array: We can use the math from Chapter 13 (Circular Queue) and expand it to allow pointers to move backward front = (front - 1 + MAX) % MAX.

• Using a Doubly Linked List (The Best Way!): Because a Doubly Linked List has prev and next pointers, and explicitly tracks the head and tail, we can effortlessly snap new nodes onto either end in O(1) time.

// Java Example: Deque using java.util.LinkedList (which IS a Doubly Linked List!)
import java.util.Deque;
import java.util.LinkedList;

public class DequeExample {
    public static void main(String[] args) {
        // We instantiate a Deque interface using the LinkedList class
        Deque<String> vipLine = new LinkedList<>();

        // Normal people join the back of the line
        vipLine.addLast("Bob");   // insertRear
        vipLine.addLast("Charlie");

        // VIP skips the line and goes straight to the front!
        vipLine.addFirst("Alice_VIP"); // insertFront

        System.out.println(vipLine); 
        // Output: [Alice_VIP, Bob, Charlie]

        // The person at the very back leaves the line early
        vipLine.removeLast(); // deleteRear
        
        System.out.println(vipLine); 
        // Output: [Alice_VIP, Bob]
    }
}

5. Variations of the Deque #

• Input-Restricted Deque: Insertions are restricted strictly to ONE end (Rear), but Deletions can occur at BOTH ends.

• Output-Restricted Deque: Deletions are restricted strictly to ONE end (Front), but Insertions can occur at BOTH ends.

6. Complexity Analysis #

7. Real-World Applications #

1. 1. Python's Default Queue: In Python, the collections.deque module is the undisputed standard for building both Stacks AND Queues, because it is hyper-optimized in C to allow O(1) appends and pops from both sides.

1. 2. Web Browser History: Navigating back and forward through recently visited URLs.

1. 3. A Palindrome Checker Algorithm: A Deque can instantly check if "RADAR" is a palindrome by simultaneously deleteFront() (R) and deleteRear() (R) and checking if they match, moving inward!

1. 4. Stealing CPU Tasks: In multi-core processing (like the Go programming language scheduler), if Core #1 finishes its task queue early, it can execute a deleteRear() on Core #2's queue, "stealing" a task from the back of the line to process it!

8. Mini Project: Palindrome Checker using Deque #

# Python Example: Palindrome check via Deque
from collections import deque

def check_palindrome(word):
    char_deque = deque(word) # Instantly creates a Deque of letters
    
    while len(char_deque) > 1:
        # Pull from both ends simultaneously!
        front_char = char_deque.popleft()
        rear_char = char_deque.pop()
        
        if front_char != rear_char:
            return False # Mismatch found!
            
    return True # Clean sweep

print(check_palindrome("racecar")) # True

9. Common Mistakes #

• Using Deques when a Stack is sufficient: A Deque is larger and more complex. If you only need LIFO behavior, mathematically restrict yourself by using a standard Stack. Don't give future developers the ability to insertFront if the business logic explicitly forbids it!

10. Best Practices #

• Master Python's Deque: If you ever take a FAANG technical interview in Python, NEVER use list.pop(0). The interviewer will fail you for executing an O(n) shift. You must explicitly import and use collections.deque.popleft() to demonstrate you understand O(1) architecture.

11. Exercises #

1. 1. Trace the contents of an empty Deque after: insertFront(1), insertRear(2), insertFront(3), deleteRear(). What is left in the Deque?

1. 2. Explain how you could use a Deque to perfectly simulate the behavior of a standard Stack. Which two operations would you restrict?

12. MCQs with Answers #

13. Interview Preparation #

• *Algorithmic Coding:* "Given an array and an integer K, find the maximum element for each and every contiguous subarray of size K. Solve this in purely O(n) time." *(Answer: The famous Sliding Window Maximum problem! It is solved optimally by utilizing a Deque to store the indexes of mathematically useful elements as the window slides right).*

Common Pitfalls:

• In whiteboard coding, attempting to implement a Deque using a Linear Array without applying the Modulo Arithmetic wrap-around logic from Chapter 13. A Linear Array Deque will instantly suffer from False Overflows on both ends!

14. FAQs #

15. Summary #

16. Next Chapter Recommendation #