Queue Concept and FIFO Principle in DSA Java - Time & Space Complexity

Time Complexity: Queue Concept and FIFO Principle

O(1)

Understanding Time Complexity

We want to understand how the time to add or remove items from a queue changes as the queue grows.

How does the queue handle operations when it gets bigger?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

public class SimpleQueue {
    private int[] items;
    private int front, rear, size, capacity;

    public SimpleQueue(int capacity) {
        this.capacity = capacity;
        items = new int[capacity];
        front = 0;
        rear = -1;
        size = 0;
    }

    public void enqueue(int item) {
        if (size == capacity) return; // queue full
        rear = (rear + 1) % capacity;
        items[rear] = item;
        size++;
    }

    public int dequeue() {
        if (size == 0) return -1; // queue empty
        int item = items[front];
        front = (front + 1) % capacity;
        size--;
        return item;
    }
}
    

This code adds (enqueue) and removes (dequeue) items following the FIFO rule in a fixed-size queue.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Adding or removing one item at a time.
• How many times: Each enqueue or dequeue runs once per operation, no loops inside.

How Execution Grows With Input

Each enqueue or dequeue takes the same amount of time no matter how many items are in the queue.

Input Size (n)	Approx. Operations per enqueue/dequeue
10	1
100	1
1000	1

Pattern observation: The time stays the same even as the queue grows.

Final Time Complexity

Time Complexity: O(1)

This means adding or removing an item takes a constant time regardless of queue size.

Common Mistake

[X] Wrong: "Removing an item from the queue takes longer as the queue gets bigger because we have to shift all items."

[OK] Correct: The queue uses front and rear pointers to track positions, so no shifting is needed. Each operation just moves a pointer, keeping time constant.

Interview Connect

Understanding that queue operations run in constant time shows you know how to use data structures efficiently, a key skill in coding interviews and real projects.

Self-Check

"What if the queue was implemented using a linked list instead of an array? How would the time complexity of enqueue and dequeue change?"

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