Queue Data Structure

# CHAPTER 12

Queue Data Structure #

1. Introduction #

2. Learning Objectives #

• Define the FIFO principle.

• Execute the core Queue operations: enqueue() and dequeue().

• Implement a Queue using a Singly Linked List to maintain O(1) performance.

• Understand why Array-based standard Queues suffer from severe memory issues.

• Build a real-world task scheduling system.

3. The Core Operations #

1. 1. enqueue(data): Inserts a new element at the Rear (Tail) of the Queue.

1. 2. dequeue(): Removes and returns the element at the Front (Head) of the Queue.

1. 3. peekFront(): Looks at the front element without removing it.

1. 4. isEmpty(): Returns True if there are zero elements in line.

4. Implementation: Linked List-Based Queue #

// Java Example: Building a Queue using a Linked List
class Node {
    int data;
    Node next;
    public Node(int d) { data = d; next = null; }
}

public class CustomQueue {
    Node front = null; // Head of list (where data leaves)
    Node rear = null;  // Tail of list (where data enters)

    // Enqueue: Add to the Rear O(1)
    public void enqueue(int data) {
        Node newNode = new Node(data);
        
        if (rear == null) { // Queue is empty!
            front = rear = newNode;
            return;
        }
        
        rear.next = newNode; // Old rear points to new node
        rear = newNode;      // New node is officially the rear
    }

    // Dequeue: Remove from the Front O(1)
    public int dequeue() {
        if (front == null) {
            System.out.println("Queue Underflow!");
            return -1;
        }
        
        int dequeuedData = front.data;
        front = front.next; // Move front pointer backward
        
        if (front == null) { // If queue becomes completely empty
            rear = null;     // Ensure rear is also reset!
        }
        return dequeuedData;
    }
}

5. The Fatal Flaw of Array-Based Queues #

1. 1. You dequeue() element A. The Front pointer moves forward.

1. 2. A new person tries to enqueue(F).

6. Complexity Analysis #

7. Real-World Applications #

1. 1. Printer Spooling: When 10 computers send print jobs to 1 printer, the printer places them in a Queue and prints them fairly in the exact order received.

1. 2. Web Server Request Handling: When 100,000 users click "Checkout" on an E-Commerce site, the Node.js server places the requests in a massive Queue (like RabbitMQ or Redis) to process them one by one without crashing the MySQL database.

1. 3. Breadth-First Search (BFS): Graph and Tree traversal algorithms utilize Queues natively to explore nodes level-by-level.

8. Mini Project: Customer Service Ticketing System #

# Python Example: Task Queue using built-in deque
from collections import deque

class SupportSystem:
    def __init__(self):
        # We use deque (Double Ended Queue) for mathematically pure O(1) ops
        self.ticket_queue = deque() 
        
    def add_ticket(self, customer_name):
        self.ticket_queue.append(customer_name) # Enqueue (Rear)
        print(f"Ticket added for: {customer_name}. Waiting in line...")
        
    def resolve_ticket(self):
        if not self.ticket_queue:
            print("No customers waiting!")
            return
        
        # Dequeue (Front)
        customer = self.ticket_queue.popleft() 
        print(f"Processing and resolving ticket for: {customer}!")

system = SupportSystem()
system.add_ticket("Alice")
system.add_ticket("Bob")
system.resolve_ticket() # Alice is processed first! (FIFO)

*(Note: Never use standard Python lists [] for Queues. Calling list.pop(0) is an O(n) operation because it physically shifts the entire array left. Always use collections.deque!)*

9. Common Mistakes #

• Using Arrays blindly for Queues: As shown in section 5, using a standard Array for a Queue without writing complex "wrap-around" mathematics will inevitably result in wasted memory and False Overflow crashes.

10. Best Practices #

• Null Reference Handing: When designing a Linked List Queue, if you dequeue the very last item in the list, front becomes null. Junior developers frequently forget to add the critical if (front == null) rear = null; logic. Without this line, the rear pointer is left pointing to "dead" memory, corrupting the entire class.

11. Exercises #

1. 1. Trace the physical layout of the Queue after these operations: enqueue(5), enqueue(10), dequeue(), enqueue(15), dequeue(). What is at the Front?

1. 2. Explain the fundamental difference between how a Stack inserts data versus how a Queue inserts data.

12. MCQs with Answers #

13. Interview Preparation #

• *Algorithmic Coding:* "Implement a fully functional Queue Class utilizing exactly TWO Stacks. How do you simulate FIFO logic using two LIFO containers?" *(Hint: Enqueue pushes data into Stack A. Dequeue pops EVERYTHING from Stack A into Stack B, completely reversing the order, and then pops the top of Stack B!).*

• *System Design:* "Explain the architectural dangers of the False Overflow state in fixed-array Queues. Propose a mathematical algorithmic solution to salvage the wasted memory space at index [0]."

Common Pitfalls:

• In whiteboard implementation, candidates frequently write dequeue logic that returns the data, but completely forgets to actually sever the memory pointer, leaving the "removed" data permanently stuck in RAM (a classic memory leak).

14. FAQs #

15. Summary #

16. Next Chapter Recommendation #