Queue in Java — Easy Cheat Sheet for Interviews

paras jainparas jain
4 min read

1. Queue Using Array

  • Logic:
    Fixed-size array with front and rear pointers.

  • Mini Code:

int arr[] = new int[size];
int front = 0, rear = 0;

void enqueue(int x) {
    arr[rear++] = x;
}

int dequeue() {
    return arr[front++];
}

Trick: Overflow if rear == size.


2. Queue Using Linked List

  • Logic:
    Dynamic nodes with front and rear pointers.

  • Mini Code:

class Node {
    int data;
    Node next;
}
Node front = null, rear = null;

void enqueue(int x) {
    Node temp = new Node();
    temp.data = x;
    if (rear == null) front = rear = temp;
    else {
        rear.next = temp;
        rear = temp;
    }
}

int dequeue() {
    int val = front.data;
    front = front.next;
    if (front == null) rear = null;
    return val;
}

Trick: No size limit, dynamic memory.


🔥 Important Queue Problems (with mini code)


1️⃣ Implement Queue Using Stacks

  • Logic: Use 2 stacks. Lazy transfer.

  • Mini Code:

Stack<Integer> s1 = new Stack<>();
Stack<Integer> s2 = new Stack<>();

void enqueue(int x) {
    s1.push(x);
}

int dequeue() {
    if (s2.isEmpty()) 
        while (!s1.isEmpty()) s2.push(s1.pop());
    return s2.pop();
}

2️⃣ Implement Circular Queue

  • Logic: (index + 1) % size.

  • Mini Code:

int[] arr = new int[size];
int front = -1, rear = -1;

void enqueue(int x) {
    if ((rear + 1) % size == front) // full
    rear = (rear + 1) % size;
    arr[rear] = x;
    if (front == -1) front = 0;
}

int dequeue() {
    int val = arr[front];
    if (front == rear) front = rear = -1; // empty
    else front = (front + 1) % size;
    return val;
}

3️⃣ Level Order Traversal (Binary Tree)

  • Logic: BFS

  • Mini Code:

Queue<TreeNode> q = new LinkedList<>();
q.add(root);

while (!q.isEmpty()) {
    TreeNode node = q.poll();
    if (node.left != null) q.add(node.left);
    if (node.right != null) q.add(node.right);
}

4️⃣ First Non-Repeating Character (Stream)

  • Logic: Queue + Freq count.

  • Mini Code:

Queue<Character> q = new LinkedList<>();
int[] freq = new int[26];

for (char ch : stream) {
    freq[ch - 'a']++;
    q.add(ch);
    while (!q.isEmpty() && freq[q.peek() - 'a'] > 1) q.poll();
}

5️⃣ Sliding Window Maximum

  • Logic: Deque for indices.

  • Mini Code:

Deque<Integer> dq = new LinkedList<>();

for (int i = 0; i < n; i++) {
    if (!dq.isEmpty() && dq.peek() == i - k) dq.poll();
    while (!dq.isEmpty() && nums[dq.peekLast()] < nums[i]) dq.pollLast();
    dq.offer(i);
    if (i >= k - 1) ans.add(nums[dq.peek()]);
}

6️⃣ Rotten Oranges

  • Logic: Multi-source BFS.

  • Mini Code:

Queue<int[]> q = new LinkedList<>();

for (all rotten oranges) q.add({i, j, 0});

while (!q.isEmpty()) {
    int[] cell = q.poll();
    for (4 directions) {
        if (fresh orange) {
            grid[x][y] = 2;
            q.add({x, y, time+1});
        }
    }
}

7️⃣ Number of Islands

  • Logic: BFS for every unvisited land.

  • Mini Code:

for (i,j) {
    if (grid[i][j] == '1') {
        bfs(i, j);
        count++;
    }
}

void bfs(int i, int j) {
    Queue<int[]> q = new LinkedList<>();
    q.add({i,j});
    while (!q.isEmpty()) {
        int[] cell = q.poll();
        mark visited;
        add all 4 neighbors if '1'
    }
}

8️⃣ Reverse a Queue

  • Logic: Recursion or Stack.

  • Mini Code:

void reverse(Queue<Integer> q) {
    if (q.isEmpty()) return;
    int x = q.poll();
    reverse(q);
    q.add(x);
}

9️⃣ Generate Binary Numbers from 1 to N

  • Logic: BFS of strings.

  • Mini Code:

Queue<String> q = new LinkedList<>();
q.add("1");

while (n-- > 0) {
    String s1 = q.poll();
    System.out.println(s1);
    q.add(s1 + "0");
    q.add(s1 + "1");
}

🧠 Full Summary Table

ProblemLogic
Queue with ArrayFront, Rear pointers
Queue with Linked ListDynamic Nodes
Queue using Stacks2 Stacks + Lazy Transfer
Circular QueueModulo operation
Level Order TraversalBFS Queue
First Non-Repeating CharacterQueue + Freq
Sliding Window MaximumDeque
Rotten OrangesBFS Multi-Source
Number of IslandsBFS per land
Reverse QueueRecursion
Generate Binary NumbersBFS on strings

Final Tip

Jaise hi "Level Order", "Stream", "Window", "Propagation", "Islands" suno —
Queue / Deque / BFS ka flash hona chahiye! 🚀

0
Subscribe to my newsletter

Read articles from paras jain directly inside your inbox. Subscribe to the newsletter, and don't miss out.

Written by

paras jain
paras jain