Search results for "DFS" | Kodesword

LeetCode 1254: Number of Closed Islands — Finding the Idea Before Writing the Code (Java)

The Honest Beginning: I Understood the Question, but I Didn't Know How to Solve ItProblem: LeetCode 1254 — Number of Closed IslandsWhen I first read this question, I understood the basic meaning of the input. We have a grid containing 0s and 1s. Zero represents land, and one represents water.But understanding the input and knowing how to solve the problem are two completely different things.The question asks us to count closed islands. What exactly is an island here? How do we decide whether several zeroes belong to the same island? And how can we tell whether an island is closed?I didn't immediately think of DFS, recursion, or connected components. Honestly, I didn't even know which direction to take.So instead of jumping straight into a solution, let's start with something familiar and build the intuition from there.Step 1: Imagine Looking for Land on a MapImagine that you are looking at a small map made up of land and water.0 means land.1 means water.Suppose several pieces of land are touching each other horizontally or vertically. Even if that land occupies many grid cells, we consider it one connected island.For example, look at this grid:1 1 1 1 11 0 0 1 11 1 0 1 11 1 1 1 1There are three land cells, but they are not three separate islands.The two zeroes in the second row are connected. The zero directly below the second zero is also connected to them.Therefore, all three cells form one island.This gives us our first important observation:We should not count every zero individually. We need to discover groups of zeroes connected in four directions: up, down, left, and right.Notice that diagonal contact does not count. Two land cells touching only at their corners are not connected under this problem's rules.But we still haven't answered the most important question: how do we discover an entire group?Step 2: How Do We Explore All the Connected Land?Suppose we find a zero at position (1, 1).What should we do next?We can inspect its four neighboring cells:Left: (1, 0)Right: (1, 2)Up: (0, 1)Down: (2, 1)If a neighboring cell contains land, we should explore that cell too. Then we should inspect its neighbors, and continue until there is no more unvisited land connected to our starting point.Think about exploring a maze. You enter a room, check the available paths, enter another room, and continue exploring. Whenever you reach a dead end or a path you have already visited, you return and try another direction.That is very close to what recursion does.We can write a function that explores a cell and calls itself for the four neighboring cells. This technique is commonly called Depth-First Search (DFS).I initially found the recursive calls confusing because it felt as if the function would keep calling itself forever. The missing piece is that we need a way to remember which cells have already been explored.In this problem, we can use the grid itself.Whenever we visit a land cell, we change its value from 0 to 1. Since we have finished treating that cell as unvisited land, we won't explore it again.This prevents us from repeatedly visiting the same cells and getting stuck in an infinite recursive loop.Step 3: Exploring an Island Is Not Enough — Is It Closed?At this point, we can discover an island. But the problem doesn't ask us to count every island. It asks us to count only closed islands.Imagine two pieces of land.In the first case, land is surrounded by water on every side. It is completely enclosed.In the second case, some land reaches the edge of the map. This island is open because it is not completely surrounded by water.The important distinction is that an island touching the boundary of the grid cannot be closed.For example:1 1 1 1 11 0 0 1 11 1 0 1 11 1 1 1 1The island is surrounded by water, so it is closed.Now consider:0 0 1 1 11 0 0 1 11 1 1 1 1The land group touches the top edge of the grid. It is not closed, even though some of its cells have water around them.This gives us the second important observation:An island is closed only if none of its connected land cells touches the boundary of the grid.We now have the complete plan:Find an unvisited land cell.Explore every land cell connected to it.Determine whether that entire island touches the boundary.Count it only if it is closed.Continue looking for other unvisited islands.The remaining challenge is implementing this logic without losing information about whether the island is open or closed.Step 4: Translating the Idea into RecursionLet's design a recursive function called sol().It receives the grid and the current row and column. It returns a boolean:true means the explored land group is closed.false means the group touches the grid boundary and is not closed.The function needs to handle three situations.Case 1: We reach waterIf the current cell contains 1, we have reached water. This direction does not lead to additional land outside the island.We return true because this particular direction does not make the island open.Case 2: We reach the grid boundaryIf the current cell is land and lies on the outermost row or column, the island touches the boundary.That means the island is not closed, so this exploration must eventually return false.However, there is a subtle implementation detail here: we must still mark and explore the boundary-connected land correctly. If we stop immediately at the first boundary cell without exploring the rest of that connected group, some of the island's cells may remain unvisited. A later scan could then mistake part of that same open island for a separate closed island.We will address this in the final implementation.Case 3: We reach unvisited interior landThis is where recursion does the real work.We mark the current cell as visited by changing it to 1. Then we explore all four directions.The island is closed only if every direction confirms that it does not connect to the outside boundary.In boolean terms, the results must be combined using logical AND (&&).If even one path reaches boundary-connected land, the whole island is open.Step 5: Connecting the Recursive Function to the Main LoopWe need a way to start exploring islands.The simplest approach is to scan the grid using two nested loops.The outer loop moves through the rows, and the inner loop moves through the columns. Whenever we find an unvisited land cell, we call our recursive function.If the function confirms that the island is closed, we increment our answer.Why can we modify the grid instead of creating a separate visited matrix?Because the original problem only requires us to return the count. We don't need to preserve the original grid, so changing visited land into water is a convenient way to remember our progress.We also need to avoid counting the same island twice. Once an entire connected island has been explored and marked, its cells will no longer trigger another DFS call from the main loop.Java SolutionHere is the complete implementation. It follows the recursive DFS approach described above and handles boundary-connected islands correctly.class Solution {public boolean sol(int[][] grid, int row, int col) {// Reaching outside the grid means this island is open.if (row < 0 || row >= grid.length ||col < 0 || col >= grid[0].length) {return false;}// Water does not make the island open.if (grid[row][col] == 1) {return true;}// Mark this land cell as visited.grid[row][col] = 1;// Explore all four directions.boolean left = sol(grid, row, col - 1);boolean right = sol(grid, row, col + 1);boolean top = sol(grid, row - 1, col);boolean bottom = sol(grid, row + 1, col);return left && right && top && bottom;}public int closedIsland(int[][] grid) {int rows = grid.length;int cols = grid[0].length;int ans = 0;for (int i = 0; i < rows; i++) {for (int j = 0; j < cols; j++) {if (grid[i][j] == 0) {if (sol(grid, i, j)) {ans++;}}}}return ans;}}What changed from my first attempt?My original code checked whether the current cell was water before checking whether it was on the boundary. It also returned immediately when isperim() detected a boundary land cell.That creates a subtle problem: the boundary cell remains unvisited, and the DFS does not continue through it to explore the rest of the connected island. Consequently, land connected through the boundary can be left behind and potentially counted incorrectly later.The revised code uses a different strategy:It checks whether the coordinates are outside the grid before accessing grid[row][col].It treats water as a successful direction.It marks every visited land cell, including boundary land.It explores all four directions before combining their results.This ensures that the whole connected island is visited, even when it is open.One more detail matters: we store the results of all four recursive calls in separate variables. This is intentional. Writing a short-circuit expression that skips later calls after the first false could leave some cells unexplored.Step 6: Dry RunConsider this grid:1 1 1 1 11 0 0 1 11 1 0 1 11 1 1 1 1The main loop scans the grid until it finds the first zero at (1, 1).First, we start DFS at (1, 1).The cell is land, so we mark it as visited. The function explores its left, right, top, and bottom neighbors.The right neighbor (1, 2) is also land. The DFS visits it and explores its neighbors.The cell (2, 2) is land as well, so the exploration continues there.Eventually, every connected land cell has been visited.Next, we check the four directions.All paths eventually reach water or the outside of the grid through no unvisited land. Because no connected land cell reaches the boundary, the recursive result is true.We increment the answer:ans = 1The main loop continues scanning. Since the three land cells have already been changed to 1, they are not counted again.There are no other land cells, so the final answer is:1This small example demonstrates the entire mechanism: one DFS call discovers the complete island, marks it visited, and returns whether it is closed.A More Important Edge Case: One Island Touching the BoundaryConsider this grid:0 0 1 1 11 0 0 1 11 1 1 1 1The connected land group touches the top boundary.When DFS starts from one of its land cells, it will eventually reach a coordinate outside the grid. That recursive call returns false.The false result propagates through the recursive calls, so the complete island is classified as open and is not counted.Because the DFS still explores all four directions and marks every land cell, the main loop cannot later count another portion of this same island as a closed island.The answer is 0.This is why visiting the complete connected group matters just as much as deciding whether it is closed.Complexity AnalysisLet m be the number of rows and n be the number of columns.Time complexity: O(m × n)Each cell is visited at most once because every visited land cell is changed from 0 to 1. The grid scan also examines every cell. Therefore, the total time complexity is O(m × n).Auxiliary space complexity: O(m × n) in the worst case.The recursive DFS can reach a depth proportional to the number of cells if a large island is connected throughout the grid. The recursion call stack can therefore use O(m × n) space in the worst case.The algorithm modifies the input grid directly and does not require a separate visited matrix.What I Learned from This ProblemThe biggest lesson was that I didn't need to know the term “connected component” before starting. I needed to understand what the problem was asking me to discover.First, I noticed that individual zeroes were not the answer; groups of connected zeroes were. That led to the idea of exploring neighbors.Then I realized that exploring one neighbor should lead to exploring its neighbors too. Recursion gave me a way to express that repeated process.Finally, I understood that a closed island was not just a group of land cells. It was a group that never reached the boundary.The difficult part was not writing four recursive calls. It was making sure the function explored the entire island and correctly communicated whether any part of it touched the boundary.That distinction is worth remembering in future DFS problems: discovering a connected group and evaluating a property of that group are two related, but separate, tasks.Final TakeawayLeetCode 1254 becomes easier to reason about once we stop thinking of it as a mysterious graph problem and start thinking of it as exploring connected land on a map.Use DFS to explore the entire island.Mark visited land so it cannot be counted twice.Treat a path that reaches outside the grid as evidence that the island is open.Count an island only when every explored direction confirms that it is closed.If you struggled to find this approach on your first attempt, that is a normal part of learning DSA. The goal is not to recognize every pattern immediately. It is to learn how to turn an unfamiliar problem into a sequence of smaller, understandable decisions.

LeetCodeJavaRecursionBacktrackingMatrixDFSMedium

Queue Data Structure Complete Guide - Java Explained With All Operations

IntroductionIf you have been learning Data Structures and Algorithms, you have probably already spent time with arrays, linked lists, and stacks. Now it is time to meet one of the most important and widely used data structures in computer science — the Queue.Queue is not just a theoretical concept. It powers some of the most critical systems you use every day — from how your printer handles jobs, to how your CPU schedules tasks, to how Google Maps finds the shortest path between two locations. Understanding Queue deeply means understanding how real systems work.In this complete guide we will cover absolutely everything — what a Queue is, how it differs from a Stack, every type of Queue, all operations with code, Java implementations, time and space complexity, common interview questions, and the most important LeetCode problems that use Queue.What Is a Queue?A Queue is a linear data structure that follows the FIFO principle — First In First Out. This means the element that was added first is the one that gets removed first.Think of it exactly like a real-world queue (a line of people). The person who joined the line first gets served first. No cutting in line, no serving from the back — strict order from front to back.This is the fundamental difference between a Queue and a Stack:Stack → LIFO (Last In First Out) — like a stack of plates, you take from the topQueue → FIFO (First In First Out) — like a line of people, you serve from the frontReal Life Examples of QueueBefore writing a single line of code, let us understand where queues appear in real life. This will make every technical concept feel natural.Printer Queue — when you send multiple documents to print, they print in the order they were sent. The first document sent prints first.CPU Task Scheduling — your operating system manages running processes in a queue. Tasks get CPU time in the order they arrive (in basic scheduling).Customer Service Call Center — when you call a helpline and are put on hold, you are placed in a queue. The first caller on hold gets connected first.WhatsApp Messages — messages are delivered in the order they are sent. The first message sent is the first one received.BFS (Breadth First Search) — every time you use Google Maps or any navigation app to find the shortest path, it uses BFS internally which is entirely powered by a Queue.Ticket Booking Systems — online booking portals process requests in the order they arrive. First come first served.Queue Terminology — Key Terms You Must KnowBefore diving into code, let us get the vocabulary right:Front — the end from which elements are removed (dequeued). This is where the "first person in line" stands.Rear (or Back) — the end at which elements are added (enqueued). New arrivals join here.Enqueue — the operation of adding an element to the rear of the queue. Like joining the back of a line.Dequeue — the operation of removing an element from the front of the queue. Like the first person in line being served and leaving.Peek (or Front) — looking at the front element without removing it. Like seeing who is first in line without serving them yet.isEmpty — checking whether the queue has no elements.isFull — relevant for fixed-size queues, checking whether no more elements can be added.Types of QueuesThis is where most beginners get confused. There is not just one type of Queue — there are several variations each designed to solve specific problems.1. Simple Queue (Linear Queue)The most basic form. Elements enter from the rear and leave from the front. Strict FIFO, nothing fancy.Enqueue → [ 1 | 2 | 3 | 4 | 5 ] → Dequeue rear frontProblem with Simple Queue: In array-based implementation, once elements are dequeued from the front, those slots cannot be reused even if there is space. This wastes memory. This is why Circular Queue was invented.2. Circular QueueIn a Circular Queue, the rear wraps around to the front when it reaches the end of the array. The last position connects back to the first, forming a circle. This solves the wasted space problem of simple queues. [1] [2] [3] / \ [6] [4] \ / [5] ← rearUsed in: CPU scheduling, memory management, traffic light systems, streaming buffers.3. Double Ended Queue (Deque)A Deque (pronounced "deck") allows insertion and deletion from both ends — front and rear. It is the most flexible queue type.Enqueue Front → [ 1 | 2 | 3 | 4 | 5 ] → Dequeue FrontEnqueue Rear → [ 1 | 2 | 3 | 4 | 5 ] → Dequeue RearTwo subtypes:Input Restricted Deque — insertion only at rear, deletion from both endsOutput Restricted Deque — deletion only at front, insertion at both endsUsed in: browser history (back and forward), undo-redo operations, sliding window problems.4. Priority QueueElements are not served in FIFO order — instead each element has a priority and the element with the highest priority is served first regardless of when it was added.Think of an emergency room. A patient with a critical injury jumps ahead of someone with a minor cut even if they arrived later.Two types:Max Priority Queue — highest value = highest priorityMin Priority Queue — lowest value = highest priorityUsed in: Dijkstra's shortest path, Huffman encoding, A* search algorithm, task scheduling with priorities.5. Blocking QueueA thread-safe queue used in multi-threading. If the queue is empty, a thread trying to dequeue will wait (block) until an element is available. If the queue is full, a thread trying to enqueue will wait until space is available.Used in: Producer-Consumer problems, thread pool implementations, Java's java.util.concurrent package.Queue Operations and Time ComplexityEvery queue operation has a specific time complexity that you must know cold for interviews.OperationDescriptionTime ComplexityEnqueueAdd element to rearO(1)DequeueRemove element from frontO(1)Peek/FrontView front elementO(1)isEmptyCheck if queue is emptyO(1)SizeNumber of elementsO(1)SearchFind a specific elementO(n)Space Complexity: O(n) — where n is the number of elements stored.All core queue operations are O(1). This is what makes Queue so powerful — no matter how many elements are in the queue, adding and removing always takes constant time.Implementing Queue in Java — All WaysJava gives you multiple ways to use a Queue. Let us go through each one.Way 1: Using LinkedList (Most Common)LinkedList implements the Queue interface in Java. This is the most commonly used Queue implementation.import java.util.LinkedList;import java.util.Queue;Queue<Integer> queue = new LinkedList<>();// Enqueue — add to rearqueue.offer(10);queue.offer(20);queue.offer(30);// Peek — view front without removingSystem.out.println(queue.peek()); // 10// Dequeue — remove from frontSystem.out.println(queue.poll()); // 10System.out.println(queue.poll()); // 20// Check emptySystem.out.println(queue.isEmpty()); // false// SizeSystem.out.println(queue.size()); // 1offer() vs add() — both add to the queue. add() throws an exception if the queue is full (for bounded queues). offer() returns false instead. Always prefer offer().poll() vs remove() — both remove from front. remove() throws an exception if queue is empty. poll() returns null. Always prefer poll().peek() vs element() — both view the front. element() throws exception if empty. peek() returns null. Always prefer peek().Way 2: Using ArrayDeque (Fastest)ArrayDeque is faster than LinkedList for Queue operations because it uses a resizable array internally with no node allocation overhead.import java.util.ArrayDeque;import java.util.Queue;Queue<Integer> queue = new ArrayDeque<>();queue.offer(1);queue.offer(2);queue.offer(3);System.out.println(queue.peek()); // 1System.out.println(queue.poll()); // 1System.out.println(queue.size()); // 2When to use ArrayDeque over LinkedList? Use ArrayDeque whenever possible for Queue or Stack operations. It is faster because it avoids the overhead of node objects that LinkedList creates for every element. In competitive programming and interviews, ArrayDeque is the preferred choice.Way 3: Using Deque (Double Ended Queue)import java.util.ArrayDeque;import java.util.Deque;Deque<Integer> deque = new ArrayDeque<>();// Add to frontdeque.offerFirst(10);// Add to reardeque.offerLast(20);deque.offerLast(30);// Remove from frontSystem.out.println(deque.pollFirst()); // 10// Remove from rearSystem.out.println(deque.pollLast()); // 30// Peek front and rearSystem.out.println(deque.peekFirst()); // 20System.out.println(deque.peekLast()); // 20Way 4: Using PriorityQueueimport java.util.PriorityQueue;// Min Heap — smallest element has highest priorityPriorityQueue<Integer> minPQ = new PriorityQueue<>();minPQ.offer(30);minPQ.offer(10);minPQ.offer(20);System.out.println(minPQ.poll()); // 10 — smallest comes out first// Max Heap — largest element has highest priorityPriorityQueue<Integer> maxPQ = new PriorityQueue<>((a, b) -> b - a);maxPQ.offer(30);maxPQ.offer(10);maxPQ.offer(20);System.out.println(maxPQ.poll()); // 30 — largest comes out firstWay 5: Implementing Queue From Scratch Using ArrayUnderstanding the underlying implementation helps you in interviews when asked to build one from scratch.class MyQueue { private int[] arr; private int front; private int rear; private int size; private int capacity; public MyQueue(int capacity) { this.capacity = capacity; arr = new int[capacity]; front = 0; rear = -1; size = 0; } public void enqueue(int val) { if (size == capacity) { System.out.println("Queue is full!"); return; } rear = (rear + 1) % capacity; // circular wrapping arr[rear] = val; size++; } public int dequeue() { if (isEmpty()) { System.out.println("Queue is empty!"); return -1; } int val = arr[front]; front = (front + 1) % capacity; // circular wrapping size--; return val; } public int peek() { if (isEmpty()) return -1; return arr[front]; } public boolean isEmpty() { return size == 0; } public int size() { return size; }}Notice the % capacity in enqueue and dequeue — that is what makes it a Circular Queue. Without this, once the rear reaches the end of the array, you cannot add more even if front has moved forward and freed up space.Way 6: Implementing Queue Using Two StacksThis is a very popular interview question — implement a Queue using two stacks. The idea is to use one stack for enqueue and another for dequeue.class QueueUsingTwoStacks { Stack<Integer> s1 = new Stack<>(); // for enqueue Stack<Integer> s2 = new Stack<>(); // for dequeue public void enqueue(int val) { s1.push(val); // always push to s1 } public int dequeue() { if (s2.isEmpty()) { // transfer all elements from s1 to s2 // this reverses the order, giving FIFO behavior while (!s1.isEmpty()) { s2.push(s1.pop()); } } return s2.pop(); } public int peek() { if (s2.isEmpty()) { while (!s1.isEmpty()) { s2.push(s1.pop()); } } return s2.peek(); } public boolean isEmpty() { return s1.isEmpty() && s2.isEmpty(); }}Why does this work?When you transfer elements from s1 to s2, the order reverses. The element that was added first to s1 ends up on top of s2 — which means it gets dequeued first. FIFO achieved using two LIFOs!Amortized time complexity: Each element is pushed and popped at most twice (once in s1, once in s2). So dequeue is O(1) amortized even though individual calls might take O(n).This is LeetCode 232 — Implement Queue using Stacks.Queue vs Stack — Side by SideFeatureQueueStackPrincipleFIFO — First In First OutLIFO — Last In First OutInsert atRearTopRemove fromFrontTopReal lifeLine of peopleStack of platesJava classLinkedList, ArrayDequeStack, ArrayDequeMain useBFS, schedulingDFS, backtracking, parsingPeekFront elementTop elementBFS — The Most Important Application of QueueBreadth First Search (BFS) is the single most important algorithm that uses a Queue. Understanding BFS is why Queue matters so much in DSA.BFS explores a graph or tree level by level — all nodes at distance 1 first, then all at distance 2, and so on. A Queue naturally enforces this level-by-level behavior.public void bfs(int start, List<List<Integer>> graph) { Queue<Integer> queue = new LinkedList<>(); boolean[] visited = new boolean[graph.size()]; queue.offer(start); visited[start] = true; while (!queue.isEmpty()) { int node = queue.poll(); // process front node System.out.print(node + " "); for (int neighbor : graph.get(node)) { if (!visited[neighbor]) { visited[neighbor] = true; queue.offer(neighbor); // add unvisited neighbors to rear } } }}Why Queue and not Stack for BFS? Queue ensures you process all neighbors of a node before going deeper. Stack would take you deep into one path first — that is DFS, not BFS. The FIFO property is what guarantees level-by-level exploration.BFS with Queue is used in:Shortest path in unweighted graphsLevel order traversal of treesFinding connected componentsWord ladder problemsRotten oranges, flood fill, and matrix BFS problemsLevel Order Traversal — BFS on TreesOne of the most common Queue problems in interviews is Level Order Traversal of a binary tree.public List<List<Integer>> levelOrder(TreeNode root) { List<List<Integer>> result = new ArrayList<>(); if (root == null) return result; Queue<TreeNode> queue = new LinkedList<>(); queue.offer(root); while (!queue.isEmpty()) { int levelSize = queue.size(); // number of nodes at current level List<Integer> level = new ArrayList<>(); for (int i = 0; i < levelSize; i++) { TreeNode node = queue.poll(); level.add(node.val); if (node.left != null) queue.offer(node.left); if (node.right != null) queue.offer(node.right); } result.add(level); } return result;}The key trick here is using queue.size() at the start of each while loop iteration to know exactly how many nodes belong to the current level. Process exactly that many nodes, then move to the next level.This is LeetCode 102 — Binary Tree Level Order Traversal.Sliding Window Maximum — Monotonic DequeOne of the most impressive Queue applications is the Sliding Window Maximum problem using a Monotonic Deque. This is the queue equivalent of the Monotonic Stack pattern you saw in stack problems.The idea — maintain a deque that stores indices of elements in decreasing order. The front always holds the index of the maximum element in the current window.public int[] maxSlidingWindow(int[] nums, int k) { Deque<Integer> deque = new ArrayDeque<>(); // stores indices int[] result = new int[nums.length - k + 1]; int idx = 0; for (int i = 0; i < nums.length; i++) { // remove indices that are out of the current window while (!deque.isEmpty() && deque.peekFirst() < i - k + 1) { deque.pollFirst(); } // remove indices whose values are smaller than current // they can never be the maximum for any future window while (!deque.isEmpty() && nums[deque.peekLast()] < nums[i]) { deque.pollLast(); } deque.offerLast(i); // window is fully formed, record maximum (front of deque) if (i >= k - 1) { result[idx++] = nums[deque.peekFirst()]; } } return result;}This gives O(n) time for what would otherwise be an O(n×k) problem. This is LeetCode 239 — Sliding Window Maximum.Java Queue Interface — Complete Method ReferenceHere is every method you will ever need from Java's Queue and Deque interfaces:Queue Methods:offer(e) — add to rear, returns false if full (preferred over add) poll() — remove from front, returns null if empty (preferred over remove) peek() — view front without removing, returns null if empty (preferred over element) isEmpty() — returns true if no elements size() — returns number of elements contains(o) — returns true if element existsDeque Additional Methods:offerFirst(e) — add to front offerLast(e) — add to rear pollFirst() — remove from front pollLast() — remove from rear peekFirst() — view front peekLast() — view rearPriorityQueue Specific:offer(e) — add with natural ordering or custom comparator poll() — remove element with highest priority peek() — view highest priority element without removingCommon Interview Questions About QueueThese are the questions interviewers ask to test your understanding of queues conceptually — not just coding.Q1. What is the difference between Queue and Stack? Queue is FIFO — elements are removed in the order they were added. Stack is LIFO — the most recently added element is removed first. Queue removes from the front, Stack removes from the top.Q2. Why is ArrayDeque preferred over LinkedList for Queue in Java? ArrayDeque uses a resizable array internally and has better cache locality and no node allocation overhead. LinkedList creates a new node object for every element added, which means more garbage collection pressure. ArrayDeque is faster in practice for most Queue use cases.Q3. When would you use a PriorityQueue instead of a regular Queue? When the order of processing depends on priority rather than arrival order. For example in a hospital, critical patients are treated before minor cases regardless of when they arrived. Or in Dijkstra's algorithm, always processing the shortest known distance first.Q4. How is Queue used in BFS? BFS uses a Queue to explore nodes level by level. The starting node is enqueued first. Each time a node is dequeued, all its unvisited neighbors are enqueued. Since Queue is FIFO, all neighbors of a node are processed before going deeper — guaranteeing level-by-level exploration.Q5. What is the difference between poll() and remove() in Java Queue? Both remove the front element. remove() throws NoSuchElementException if the queue is empty. poll() returns null instead of throwing. Always use poll() for safer code.Q6. Can a Queue have duplicates? Yes. Queue does not have any restriction on duplicate values unlike Sets. The same value can appear multiple times in a Queue.Q7. What is a Blocking Queue and when is it used? A Blocking Queue is a thread-safe Queue used in multi-threaded applications. When a thread tries to dequeue from an empty queue, it blocks (waits) until an element is available. When a thread tries to enqueue into a full queue, it blocks until space is available. Used in Producer-Consumer patterns.Top LeetCode Problems on QueueHere are the most important LeetCode problems that use Queue — organized from beginner to advanced:Beginner Level:232. Implement Queue using Stacks — implement Queue with two stacks, classic interview question225. Implement Stack using Queues — reverse of 232, implement Stack using Queue933. Number of Recent Calls — sliding window with QueueIntermediate Level:102. Binary Tree Level Order Traversal — BFS on tree, must know107. Binary Tree Level Order Traversal II — same but bottom up994. Rotting Oranges — multi-source BFS on grid1091. Shortest Path in Binary Matrix — BFS shortest path542. 01 Matrix — multi-source BFS, distance to nearest 0127. Word Ladder — BFS on word graph, classicAdvanced Level:239. Sliding Window Maximum — monotonic deque, must know862. Shortest Subarray with Sum at Least K — monotonic deque with prefix sums407. Trapping Rain Water II — 3D BFS with priority queue787. Cheapest Flights Within K Stops — BFS with constraintsQueue Cheat Sheet — Everything at a GlanceCreate a Queue:Queue<Integer> q = new LinkedList<>(); // standardQueue<Integer> q = new ArrayDeque<>(); // faster, preferredDeque<Integer> dq = new ArrayDeque<>(); // double endedPriorityQueue<Integer> pq = new PriorityQueue<>(); // min heapPriorityQueue<Integer> pq = new PriorityQueue<>((a,b) -> b-a); // max heapCore Operations:q.offer(x); // enqueueq.poll(); // dequeueq.peek(); // front elementq.isEmpty(); // check emptyq.size(); // number of elementsDeque Operations:dq.offerFirst(x); // add to frontdq.offerLast(x); // add to reardq.pollFirst(); // remove from frontdq.pollLast(); // remove from reardq.peekFirst(); // view frontdq.peekLast(); // view rearBFS Template:Queue<Integer> queue = new LinkedList<>();queue.offer(start);visited[start] = true;while (!queue.isEmpty()) { int node = queue.poll(); for (int neighbor : graph.get(node)) { if (!visited[neighbor]) { visited[neighbor] = true; queue.offer(neighbor); } }}ConclusionQueue is one of those data structures that appears simple on the surface but has incredible depth once you start exploring its variations and applications. From the basic FIFO concept to Circular Queues, Deques, Priority Queues, Monotonic Deques, and BFS — each layer adds a new tool to your problem-solving arsenal.Here is the learning path to follow based on everything covered in this guide:Start with understanding FIFO vs LIFO and when each applies. Then get comfortable with Java's Queue interface — offer, poll, peek. Practice the BFS template until it feels automatic. Then move to Level Order Traversal problems. Once BFS clicks, tackle multi-source BFS problems like Rotting Oranges. Finally learn the Monotonic Deque pattern for sliding window problems.Master these and you will handle every Queue problem in any coding interview with confidence.

QueueData StructureJavaBFSDequePriority QueueCircular Queue

Search Blogs

LeetCode 1306: Jump Game III – Java DFS & Graph Traversal Solution Explained

LeetCode 2265: Count Nodes Equal to Average of Subtree – Java DFS Solution

LeetCode 1254: Number of Closed Islands — Finding the Idea Before Writing the Code (Java)

LeetCode 102: Binary Tree Level Order Traversal – Java BFS Solution Explained

LeetCode 110: Balanced Binary Tree – Java Optimized DFS Solution Explained

LeetCode 543: Diameter of Binary Tree – Java DFS Solution Explained

LeetCode 104: Maximum Depth of Binary Tree – Java Recursive Solution Explained

LeetCode 144: Binary Tree Preorder Traversal – Java Recursive & Iterative Solution Explained

LeetCode 124: Binary Tree Maximum Path Sum – Java DFS Solution Explained

LeetCode 98: Validate Binary Search Tree – Java DFS Recursive Solution Explained

LeetCode 145: Binary Tree Postorder Traversal – Java Recursive & Iterative Solution Explained

LeetCode 94: Binary Tree Inorder Traversal – Java Recursive & Iterative Solution Explained

LeetCode 230: Kth Smallest Element in a BST – Java Recursive Inorder Traversal Solution

LeetCode 701: Insert into a Binary Search Tree – Java Recursive Solution with Dry Run

Queue Data Structure Complete Guide - Java Explained With All Operations

LeetCode 39: Combination Sum – Java Backtracking Solution with Dry Run & Complexity

LeetCode 3963: Create Grid With Exactly One Path — The Simple Java Trick I Almost Overlooked

Ai Assistant Kas