Queue: FIFO and Deque Code Templates in 6 Languages

Coding Patterns - Guide to 30 Core Algorithm Patterns

Queue: Complete Guide with FIFO, Deque, and BFS Examples

If you have not read the concept guide yet, start there for the intuition and complexity analysis. This page gives you the code you can memorize and adapt during an interview. Every template here keeps the hard parts in the comments, and the hard parts are the visited check in BFS, the size snapshot in level order, and the eviction rules in the monotonic deque.

Main Template: FIFO Queue for BFS

The single most common interview use of a queue is breadth-first search. The queue holds the frontier of nodes to visit, and the visited set is what keeps the frontier from exploding. This template produces the shortest number of steps to every reachable node, which is exactly what shortest-path style problems ask for.

Use this for Open the Lock and similar shortest-step problems.

    graph TD
    S["Enqueue start, mark visited"] --> Q{"Queue not empty?"}
    Q -->|Yes| D["Dequeue node"]
    D --> N["For each neighbor"]
    N --> V{"Visited?"}
    V -->|No| A["Mark visited, enqueue"]
    A --> Q
    V -->|Yes| Q
    Q -->|No| E["Done"]

function bfs(graph, start) {
  const queue = [start];
  const visited = new Set([start]);

  while (queue.length > 0) {
      const node = queue.shift();

      for (const neighbor of graph[node] || []) {
          // Mark at enqueue time, not dequeue time. The first
          // time we reach a node is already the shortest path,
          // so later discoveries are pure duplicates.
          if (!visited.has(neighbor)) {
              visited.add(neighbor);
              queue.push(neighbor);
          }
      }
  }
  return visited;
}

from collections import deque

def bfs(graph, start):
  queue = deque([start])
  visited = {start}

  while queue:
      node = queue.popleft()

      for neighbor in graph.get(node, []):
          # Marking on enqueue keeps the queue at O(V).
          # Marking on dequeue would let the same node be
          # enqueued once per incoming edge, O(E) elements.
          if neighbor not in visited:
              visited.add(neighbor)
              queue.append(neighbor)

  return visited

import java.util.*;

Set<Integer> bfs(Map<Integer, List<Integer>> graph, int start) {
  Queue<Integer> queue = new LinkedList<>();
  Set<Integer> visited = new HashSet<>();

  queue.offer(start);
  visited.add(start);

  while (!queue.isEmpty()) {
      int node = queue.poll();

      for (int neighbor : graph.getOrDefault(node, List.of())) {
          if (!visited.contains(neighbor)) {
              visited.add(neighbor);
              queue.offer(neighbor);
          }
      }
  }
  return visited;
}

#include <queue>
#include <unordered_set>
#include <unordered_map>
#include <vector>

std::unordered_set<int> bfs(
  const std::unordered_map<int, std::vector<int>>& graph, int start) {
  std::queue<int> queue;
  std::unordered_set<int> visited;

  queue.push(start);
  visited.insert(start);

  while (!queue.empty()) {
      int node = queue.front();
      queue.pop();

      for (int neighbor : graph.at(node)) {
          if (!visited.count(neighbor)) {
              visited.insert(neighbor);
              queue.push(neighbor);
          }
      }
  }
  return visited;
}

The complexity of this shape is

O(V + E)

time and

O(V)

space. Every node is enqueued once because of the visited check, and every edge is examined from its source exactly once.

Templates only help if you can recall them without staring at the screen. Turn these snippets into flashcards for daily mobile review.

Code Breakdown

Key Variables

queue: the frontier of nodes waiting to be processed. FIFO order means every node at distance d is dequeued before any node at distance d+1.
visited: nodes already discovered. Without it, a cycle sends the loop into an infinite queue, and a diamond in the graph processes the same node multiple times.
graph[node]: the neighbors of a node. In trees it becomes left and right; in grids it becomes the four directions.

Visual Mechanism

The diagram above is the whole pattern: initialize, loop while the queue has anything, and mark visited when you enqueue. The rest of every BFS problem is deciding what “visited” means and what to return.

Critical Sections

The visited check belongs inside the neighbor loop, before the enqueue. If you mark a node only when it comes out of the queue, two neighbors that both discover the same third node will both add it, and the queue grows to the edge count instead of the node count. The result is the same visited set, but the runtime silently turns quadratic on dense graphs.

The result assembly depends on the problem. For reachability, visited alone computes it. For shortest path, you pair the visited set with a distance map and return the distance entry for the target.

Variations

1. Level-Order Traversal (Size Snapshot)

Read the queue size once per level. Process exactly that many nodes, then the queue holds exactly the next level. This is the classic Binary Tree Level Order Traversal shape and generalizes to “process by distance”.

Used in problems like Binary Tree Level Order Traversal and shortest-path problems that report counts per layer.

function levelOrder(root) {
  const result = [];
  if (!root) return result;

  const queue = [root];

  while (queue.length > 0) {
      const levelSize = queue.length; // snapshot BEFORE processing
      const currentLevel = [];

      for (let i = 0; i < levelSize; i++) {
          const node = queue.shift();
          currentLevel.push(node.val);

          if (node.left) queue.push(node.left);
          if (node.right) queue.push(node.right);
      }
      result.push(currentLevel);
  }
  return result;
}

def level_order(root):
  result = []
  if not root:
      return result

  queue = deque([root])

  while queue:
      level_size = len(queue)  # snapshot the current layer
      current_level = []

      for _ in range(level_size):
          node = queue.popleft()
          current_level.append(node.val)

          if node.left:
              queue.append(node.left)
          if node.right:
              queue.append(node.right)

      result.append(current_level)

  return result

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(); // snapshot the current layer
      List<Integer> currentLevel = new ArrayList<>();

      for (int i = 0; i < levelSize; i++) {
          TreeNode node = queue.poll();
          currentLevel.add(node.val);

          if (node.left != null) queue.offer(node.left);
          if (node.right != null) queue.offer(node.right);
      }
      result.add(currentLevel);
  }
  return result;
}

#include <queue>
#include <vector>

std::vector<std::vector<int>> levelOrder(TreeNode* root) {
  std::vector<std::vector<int>> result;
  if (!root) return result;
  std::queue<TreeNode*> q;
  q.push(root);

  while (!q.empty()) {
      int levelSize = q.size();
      std::vector<int> currentLevel;

      for (int i = 0; i < levelSize; i++) {
          TreeNode* node = q.front();
          q.pop();
          currentLevel.push_back(node->val);

          if (node->left) q.push(node->left);
          if (node->right) q.push(node->right);
      }
      result.push_back(currentLevel);
  }
  return result;
}

func levelOrder(root *TreeNode) [][]int {
  result := [][]int{}
  if root == nil {
      return result
  }

  queue := []*TreeNode{root}

  for len(queue) > 0 {
      levelSize := len(queue)
      currentLevel := []int{}

      for i := 0; i < levelSize; i++ {
          node := queue[0]
          queue = queue[1:]
          currentLevel = append(currentLevel, node.Val)

          if node.Left != nil {
              queue = append(queue, node.Left)
          }
          if node.Right != nil {
              queue = append(queue, node.Right)
          }
      }
      result = append(result, currentLevel)
  }
  return result
}

def level_order(root)
result = []
return result unless root

queue = [root]

until queue.empty?
  level_size = queue.size # snapshot the current layer
  current_level = []

  level_size.times do
    node = queue.shift
    current_level << node.val

    queue << node.left if node.left
    queue << node.right if node.right
  end

  result << current_level
end

result
end

The snapshot is the whole trick. Processing with a live length check mixes the next level into the current one. Take the size first, loop exactly that many times, then the outer loop naturally starts the next level.

The complexity is

O(N)

time and

O(N)

space in the worst case. Each node enters the queue exactly once, and the queue can hold a full level of nodes at its widest point.

Level order is one of the most asked binary tree questions with a queue, and the size snapshot is its one subtle line. Make it a flashcard: it is a review card in our app. Practice the variations with a review queue and the snapshot logic will be automatic.

2. Monotonic Deque (Sliding Window Maximum)

Use this when the window slides and you need the maximum element of every window in

O(N)

time. A deque that stores candidate indices in decreasing value order makes the front always the maximum of the current window.

    graph LR
    A["New index i"] --> B{"Front < i - k + 1?"}
    B -->|Yes| C["Pop front (out of window)"]
    C --> D{"Back value <= nums[i]?"}
    D -->|Yes| E["Pop back"]
    D -->|No| F["Push i"]
    E --> D
    F --> G{"i >= k-1?"}
    G -->|Yes| H["Output front value"]

Use this for Sliding Window Maximum .

var maxSlidingWindow = function(nums, k) {
  const result = [];
  const deque = []; // stores indices, in decreasing value order

  for (let i = 0; i < nums.length; i++) {
      // Evict indices that have slid out of the window.
      while (deque.length > 0 && deque[0] < i - k + 1) {
          deque.shift();
      }
      // Evict indices whose value loses to the new one. The
      // new element is both larger and lives longer in the
      // window, so the old one can never be the answer.
      while (deque.length > 0 && nums[deque[deque.length - 1]] <= nums[i]) {
          deque.pop();
      }
      deque.push(i);

      if (i >= k - 1) {
          result.push(nums[deque[0]]);
      }
  }
  return result;
};

from collections import deque

def max_sliding_window(nums: List[int], k: int) -> List[int]:
  result = []
  dq = deque()  # stores indices, values in decreasing order

  for i, num in enumerate(nums):
      # Drop indices that slid out of the window.
      while dq and dq[0] < i - k + 1:
          dq.popleft()
      # Drop smaller tail values: the new value is later and
      # large at least as big, so the older one cannot win.
      while dq and nums[dq[-1]] <= num:
          dq.pop()
      dq.append(i)

      if i >= k - 1:
          result.append(nums[dq[0]])

  return result

public int[] maxSlidingWindow(int[] nums, int k) {
  int n = nums.length;
  int[] result = new int[n - k + 1];
  Deque<Integer> deque = new ArrayDeque<>(); // stores indices

  for (int i = 0; i < n; i++) {
      while (!deque.isEmpty() && deque.peekFirst() < i - k + 1) {
          deque.pollFirst();
      }
      while (!deque.isEmpty() && nums[deque.peekLast()] <= nums[i]) {
          deque.pollLast();
      }
      deque.offerLast(i);

      if (i >= k - 1) {
          result[i - k + 1] = nums[deque.peekFirst()];
      }
  }
  return result;
}

#include <deque>
#include <vector>

std::vector<int> maxSlidingWindow(std::vector<int>& nums, int k) {
  std::vector<int> result;
  std::deque<int> dq; // stores indices

  for (int i = 0; i < nums.size(); i++) {
      while (!dq.empty() && dq.front() < i - k + 1) {
          dq.pop_front();
      }
      while (!dq.empty() && nums[dq.back()] <= nums[i]) {
          dq.pop_back();
      }
      dq.push_back(i);

      if (i >= k - 1) {
          result.push_back(nums[dq.front()]);
      }
  }
  return result;
}

func maxSlidingWindow(nums []int, k int) []int {
  result := []int{}
  dq := []int{} // stored indices

  for i := 0; i < len(nums); i++ {
      for len(dq) > 0 && dq[0] < i-k+1 {
          dq = dq[1:]
      }
      for len(dq) > 0 && nums[dq[len(dq)-1]] <= nums[i] {
          dq = dq[:len(dq)-1]
      }
      dq = append(dq, i)

      if i >= k-1 {
          result = append(result, nums[dq[0]])
      }
  }
  return result
}

Each index is pushed and popped at most once, so the total cost is

O(N)

time and

O(k)

space. The deque membership rule is “decreasing values”. You can flip it to “increasing values” with one symbol change and get the window minimum instead.

Each variation above is a separate review card in the app. Drill them individually so you don’t mix up the conditions under pressure.

Next Steps

Both templates are now memorized, or close to it. The quickest way to lock in is application, so head to the practice problems page and work with these templates on real inputs. That page also links to related patterns to expand further.

Now that you have the templates, the next step is application. Head to the practice problems or start reviewing these templates with spaced repetition .