Queues in Java

Queues are a fundamental data structure in Java and are widely used in Leetcode problems. They follow the First-In-First-Out (FIFO) principle, meaning the first element added is the first one to be removed.

---

Table of Contents

1. Queue Basics
2. Common Queue Operations
3. Deque (Double Ended Queue)
4. Priority Queue
5. Common Leetcode Patterns
6. Time and Space Complexity
7. Related Leetcode Questions

---

Queue Basics

• Definition: A queue is a linear data structure that follows the FIFO principle. Elements are added at the rear (enqueue) and removed from the front (dequeue).

• Declaration:

  import java.util.LinkedList;
  import java.util.Queue;
  
  Queue<Integer> queue = new LinkedList<>();

• Key Characteristics:

  • FIFO (First-In-First-Out) order.
  • Commonly implemented using LinkedList in Java.
  • Supports operations like add, remove, peek, etc.

---

Common Queue Operations

1. Adding an Element (Enqueue)

• Method: add(E e) or offer(E e)
• Example:

  queue.add(1);
  queue.offer(2);

• Time Complexity: O(1)
• Space Complexity: O(1)

2. Removing an Element (Dequeue)

• Method: remove() or poll()
• Example:

  int element = queue.remove(); // Removes and returns the front element
  int element = queue.poll();   // Returns null if the queue is empty

• Time Complexity: O(1)
• Space Complexity: O(1)

3. Peeking at the Front Element

• Method: element() or peek()
• Example:

  int frontElement = queue.element(); // Throws exception if the queue is empty
  int frontElement = queue.peek();    // Returns null if the queue is empty

• Time Complexity: O(1)
• Space Complexity: O(1)

4. Checking if the Queue is Empty

• Method: isEmpty()
• Example:

  boolean isEmpty = queue.isEmpty(); // isEmpty = false

• Time Complexity: O(1)
• Space Complexity: O(1)

5. Size of the Queue

• Method: size()
• Example:

  int size = queue.size(); // size = 2

• Time Complexity: O(1)
• Space Complexity: O(1)

---

Deque (Double Ended Queue)

• Definition: A deque (double-ended queue) is a linear data structure that allows insertion and deletion at both ends.

• Declaration:

  import java.util.Deque;
  import java.util.LinkedList;
  
  Deque<Integer> deque = new LinkedList<>();

• Key Characteristics:

  • Allows insertion and deletion at both ends.
  • Commonly implemented using LinkedList in Java.
  • Supports operations like addFirst, addLast, removeFirst, removeLast, etc.

Common Deque Operations

1. Adding an Element at the Front

• Method: addFirst(E e) or offerFirst(E e)
• Time Complexity: O(1)
• Space Complexity: O(1)

2. Adding an Element at the Rear

• Method: addLast(E e) or offerLast(E e)
• Time Complexity: O(1)
• Space Complexity: O(1)

3. Removing an Element from the Front

• Method: removeFirst() or pollFirst()
• Time Complexity: O(1)
• Space Complexity: O(1)

4. Removing an Element from the Rear

• Method: removeLast() or pollLast()
• Time Complexity: O(1)
• Space Complexity: O(1)

5. Peeking at the Front Element

• Method: getFirst() or peekFirst()
• Time Complexity: O(1)
• Space Complexity: O(1)

6. Peeking at the Rear Element

• Method: getLast() or peekLast()
• Time Complexity: O(1)
• Space Complexity: O(1)

---

Priority Queue

• Definition: A priority queue is a data structure that stores elements with associated priorities. Elements are dequeued based on their priority.

• Declaration:

  import java.util.PriorityQueue;
  
  PriorityQueue<Integer> pq = new PriorityQueue<>(); // Min Heap
  PriorityQueue<Integer> maxHeap = new PriorityQueue<>((a, b) -> b - a); // Max Heap

• Key Characteristics:

  • Elements are dequeued based on priority.
  • Commonly implemented using PriorityQueue in Java.
  • Supports operations like add, remove, peek, etc.

Common Priority Queue Operations

1. Adding an Element

• Method: add(E e) or offer(E e)
• Time Complexity: O(log n)
• Space Complexity: O(1)

2. Removing an Element

• Method: remove() or poll()
• Time Complexity: O(log n)
• Space Complexity: O(1)

3. Peeking at the Highest Priority Element

• Method: peek()
• Time Complexity: O(1)
• Space Complexity: O(1)

4. Checking if the Priority Queue is Empty

• Method: isEmpty()
• Time Complexity: O(1)
• Space Complexity: O(1)

5. Size of the Priority Queue

• Method: size()
• Time Complexity: O(1)
• Space Complexity: O(1)

---

Common Leetcode Patterns

1. Breadth-First Search (BFS)

• Used for problems like level-order traversal, shortest path in unweighted graphs, etc.
• Example:

  Queue<TreeNode> queue = new LinkedList<>();
  queue.add(root);
  while (!queue.isEmpty()) {
      TreeNode node = queue.poll();
      System.out.println(node.val);
      if (node.left != null) queue.add(node.left);
      if (node.right != null) queue.add(node.right);
  }

• Related Questions:
  • Binary Tree Level Order Traversal
  • Shortest Path in Binary Matrix
  • Word Ladder

2. Sliding Window

• Used for problems like maximum sliding window, first negative number in every window, etc.
• Example:

  Deque<Integer> deque = new LinkedList<>();
  for (int i = 0; i < nums.length; i++) {
      while (!deque.isEmpty() && nums[deque.peekLast()] < nums[i]) {
          deque.pollLast();
      }
      deque.addLast(i);
      if (deque.peekFirst() == i - k) {
          deque.pollFirst();
      }
      if (i >= k - 1) {
          result[i - k + 1] = nums[deque.peekFirst()];
      }
  }

• Related Questions:
  • Sliding Window Maximum
  • First Negative Number in Every Window

3. Implementing Stacks Using Queues

• Used for problems like implementing a stack using queues, queue using stacks, etc.
• Example:

  Queue<Integer> queue = new LinkedList<>();
  public void push(int x) {
      queue.add(x);
      for (int i = 1; i < queue.size(); i++) {
          queue.add(queue.remove());
      }
  }
  public int pop() {
      return queue.remove();
  }

• Related Questions:
  • Implement Stack using Queues
  • Implement Queue using Stacks

4. Circular Queue

• Used for problems like designing a circular queue, implementing a circular buffer, etc.
• Example:

  class MyCircularQueue {
      int[] queue;
      int front, rear, size, capacity;
      public MyCircularQueue(int k) {
          queue = new int[k];
          front = 0; rear = -1; size = 0; capacity = k;
      }
      public boolean enQueue(int value) {
          if (isFull()) return false;
          rear = (rear + 1) % capacity;
          queue[rear] = value;
          size++;
          return true;
      }
      public boolean deQueue() {
          if (isEmpty()) return false;
          front = (front + 1) % capacity;
          size--;
          return true;
      }
      public int Front() {
          return isEmpty() ? -1 : queue[front];
      }
      public int Rear() {
          return isEmpty() ? -1 : queue[rear];
      }
      public boolean isEmpty() {
          return size == 0;
      }
      public boolean isFull() {
          return size == capacity;
      }
  }

• Related Questions:
  • Design Circular Queue
  • Design Circular Deque

5. Priority Queue Patterns

• Used for problems like kth largest element, merge k sorted lists, heap sort, etc.
• Example:

  PriorityQueue<Integer> pq = new PriorityQueue<>();
  for (int num : nums) {
      pq.add(num);
      if (pq.size() > k) {
          pq.poll();
      }
  }
  return pq.peek();

• Related Questions:
  • Kth Largest Element in an Array
  • Merge k Sorted Lists
  • Heap Sort

---

Time and Space Complexity

Operation	Time Complexity	Space Complexity
Enqueue (add(), offer())	O(1)	O(1)
Dequeue (remove(), poll())	O(1)	O(1)
Peek (element(), peek())	O(1)	O(1)
Is Empty (isEmpty())	O(1)	O(1)
Size (size())	O(1)	O(1)
Deque Operations
Add First/Last	O(1)	O(1)
Remove First/Last	O(1)	O(1)
Peek First/Last	O(1)	O(1)
Priority Queue Operations
Add (add(), offer())	O(log n)	O(1)
Remove (remove(), poll())	O(log n)	O(1)
Peek (peek())	O(1)	O(1)

---

Related Leetcode Questions

Easy

1. Implement Queue using Stacks
2. Number of Recent Calls
3. Moving Average from Data Stream

Medium

1. Binary Tree Level Order Traversal
2. Sliding Window Maximum
3. Design Circular Queue
4. Kth Largest Element in an Array

Hard

1. Word Ladder
2. Shortest Path in Binary Matrix
3. Design Circular Deque
4. Merge k Sorted Lists

---

Save this to your queue.md file and use it as a quick reference while solving Leetcode problems!