Queue Concept and FIFO Principle in DSA Java

Mental Model

A queue is a line where the first person in is the first person out. We add items at the back and remove from the front.

Analogy: Imagine waiting in line at a grocery store checkout. The first person to get in line is the first to be served and leave the line.

front -> [1] -> [2] -> [3] -> back
↑ enqueue here
← dequeue here

Dry Run Walkthrough

Input: Start with empty queue, enqueue 1, enqueue 2, enqueue 3, then dequeue one item

Goal: Show how items enter at the back and leave from the front following FIFO

Step 1: enqueue 1 at back

front -> [1] -> back
↑ enqueue here
← dequeue here

Why: We add the first item to the empty queue at the back

Step 2: enqueue 2 at back

front -> [1] -> [2] -> back
↑ enqueue here
← dequeue here

Why: New item goes behind the existing one, keeping order

Step 3: enqueue 3 at back

front -> [1] -> [2] -> [3] -> back
↑ enqueue here
← dequeue here

Why: Add another item at the back, queue grows

Step 4: dequeue from front (remove 1)

front -> [2] -> [3] -> back
↑ enqueue here
← dequeue here

Why: Remove the first item that entered, following FIFO

Result:

front -> [2] -> [3] -> back
Queue after dequeue: 2 -> 3 -> null

Annotated Code

DSA Java

import java.util.LinkedList;
import java.util.Queue;

public class QueueExample {
    public static void main(String[] args) {
        Queue<Integer> queue = new LinkedList<>();

        // enqueue 1
        queue.add(1); // add at back
        // enqueue 2
        queue.add(2); // add at back
        // enqueue 3
        queue.add(3); // add at back

        // dequeue one item
        Integer removed = queue.poll(); // remove from front

        // print queue
        printQueue(queue);
        System.out.println("Dequeued item: " + removed);
    }

    private static void printQueue(Queue<Integer> queue) {
        for (Integer item : queue) {
            System.out.print(item + " -> ");
        }
        System.out.println("null");
    }
}

queue.add(1); // add at back

enqueue first item at the back of the queue

queue.add(2); // add at back

enqueue second item at the back

queue.add(3); // add at back

enqueue third item at the back

Integer removed = queue.poll(); // remove from front

dequeue the front item following FIFO

printQueue(queue);

print current queue state after dequeue

Output

2 -> 3 -> null

Dequeued item: 1

Complexity Analysis

Time: O(1) for enqueue and dequeue because adding or removing from ends of linked list is constant time

Space: O(n) because queue stores n elements

vs Alternative: Compared to using an array where dequeue might require shifting elements O(n), linked list queue is more efficient

Edge Cases

dequeue from empty queue

poll() returns null safely without error

DSA Java

Integer removed = queue.poll(); // remove from front

enqueue null value

LinkedList queue allows null but it may cause confusion; best to avoid

DSA Java

queue.add(1); // add at back (no explicit null check)

When to Use This Pattern

When a problem requires processing items in the exact order they arrive, use a queue with FIFO principle to maintain order.

Common Mistakes

Mistake: Using stack (LIFO) instead of queue (FIFO) for order-sensitive tasks
Fix: Use queue data structure methods add() and poll() to maintain FIFO order

Mistake: Removing items from the back instead of front
Fix: Always remove from front using poll() to follow FIFO

Summary

A queue stores items so the first added is the first removed (FIFO).

Use a queue when order of processing matters, like waiting lines or task scheduling.

The key is adding at the back and removing from the front to keep order.

Practice

1. What does the FIFO principle mean in the context of a queue?

easy

A. Last In, First Out - the last element added is the first removed

B. First In, Last Out - the first element added is the last removed

C. First In, First Out - the first element added is the first removed

D. Last In, Last Out - the last element added is the last removed

Solution

1. Step 1: Understand FIFO meaning

   FIFO means the first element that enters the queue is the first to leave.

2. Step 2: Match FIFO to queue behavior

   Queues follow FIFO, so the first added element is removed first.

3. Final Answer:

   First In, First Out - the first element added is the first removed -> Option C

4. Quick Check:

   FIFO = First In, First Out [OK]

Hint: Remember queue = line; first come, first served [OK]

Common Mistakes:

• Confusing FIFO with LIFO
• Thinking queue removes last added first
• Mixing stack behavior with queue

2. Which of the following is the correct way to add an element to a Java Queue named q?

easy

A. q.add(10);

B. q.enqueue(10);

C. q.push(10);

D. q.insert(10);

Solution

1. Step 1: Recall Java Queue methods

   Java Queue interface uses add() or offer() to add elements.

2. Step 2: Identify correct method

   push() and enqueue() are not Queue methods; insert() is invalid.

3. Final Answer:

   q.add(10); -> Option A

4. Quick Check:

   Use add() to insert in Java Queue [OK]

Hint: Use add() or offer() to add in Java Queue [OK]

Common Mistakes:

• Using push() which is for stacks
• Using enqueue() which is not a Java Queue method
• Using insert() which does not exist in Queue

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

import java.util.*;
public class Main {
  public static void main(String[] args) {
    Queue<Integer> q = new LinkedList<>();
    q.add(5);
    q.add(10);
    q.add(15);
    System.out.print(q.poll() + " -> ");
    System.out.print(q.poll() + " -> ");
    System.out.print(q.poll() + " -> ");
  }
}

medium

A. 15 -> 10 -> 5 ->

B. 5 -> 10 -> 15 ->

C. 10 -> 15 -> 5 ->

D. 5 -> 15 -> 10 ->

Solution

1. Step 1: Add elements to queue

   Elements 5, 10, 15 are added in order to the queue.

2. Step 2: Remove elements using poll()

   poll() removes elements in FIFO order: 5, then 10, then 15.

3. Final Answer:

   5 -> 10 -> 15 -> -> Option B

4. Quick Check:

   Queue poll() removes in FIFO order [OK]

Hint: poll() removes first added element in queue [OK]

Common Mistakes:

• Thinking poll() removes last element
• Confusing queue with stack order
• Assuming poll() does not remove element

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

Queue<String> q = new LinkedList<>();
q.add("apple");
q.add("banana");
String first = q.remove();
String second = q.remove();
String third = q.remove();

medium

A. No error, code runs fine

B. remove() method does not exist in Queue

C. Queue cannot store Strings

D. Third remove() causes NoSuchElementException

Solution

1. Step 1: Check number of elements added

   Only two elements "apple" and "banana" are added to the queue.

2. Step 2: Analyze remove() calls

   First two remove() calls remove "apple" and "banana". Third remove() tries to remove from empty queue causing exception.

3. Final Answer:

   Third remove() causes NoSuchElementException -> Option D

4. Quick Check:

   Removing from empty queue throws exception [OK]

Hint: Removing more than added elements causes exception [OK]

Common Mistakes:

• Assuming remove() returns null if empty
• Thinking queue can't store Strings
• Believing remove() method is missing

5. You have a queue that stores customer IDs in order of arrival. You want to process customers but skip any ID that is negative (invalid). Which approach correctly processes the queue while maintaining FIFO order and skipping negatives?

Queue<Integer> q = new LinkedList<>();
// Assume q is filled with IDs including negatives
while (!q.isEmpty()) {
  int id = q.poll();
  // What to do here?
}

hard

A. If id is negative, ignore and continue; else process it

B. If id is negative, remove all remaining elements

C. If id is negative, stop processing the queue

D. If id is negative, add it back to the end of the queue

Solution

1. Step 1: Understand queue processing with condition

   We want to skip negative IDs but keep processing others in order.

2. Step 2: Choose correct action for negative IDs

   Ignoring negative IDs and continuing preserves FIFO order and processes valid IDs only.

3. Final Answer:

   If id is negative, ignore and continue; else process it -> Option A

4. Quick Check:

   Skip negatives, process others in FIFO [OK]

Hint: Skip invalid IDs, don't re-add or stop queue [OK]

Common Mistakes:

• Re-adding negative IDs causing infinite loop
• Stopping queue on first negative ID
• Removing all elements on negative ID