Tutorials

/

Interviewing

/

Queues

Previous:

Stacks

Next:

Recursion

Queues

September 17, 2023

At this point, you’ve seen techniques for solving interview questions that involve various data structures, including maps, sets, and stacks.

Similar to Stack data structures, Queue data structures provide functions that work more efficiently for certain circumstances. Specifically, Queue data structures are handy when you need to add elements to the “back” of your collection, and remove them from the “front” of it.

You could get this functionality using an ArrayList where you only add or remove elements from each end. But at least one of the operations (add or remove) is going to require shifting the entire list, which will make it linear O(n) time. The power of Queue data structures is that adding and removing from them is more efficient.

Queue vs Deque

Java contains a few different queue interfaces and classes:

• Queue is an interface that declares functions like add() and remove()
  • PriorityQueue is a class that implements Queue and maintains the order of its elements
  • Deque is a subinterface that declares functions that define a double-ended queue
    • LinkedList is an older class, but it’s more efficient if you need to insert a new element while you’re iterating (in other words, if you aren’t treating it as a queue). The LinkedList class also offers a get(index) function, but that runs in linear time and is also outside the bounds of the traditional queue data structure.
    • ArrayDeque is newer, and is the most common (double ended) queue class in Java. This class can also be used as a stack, so it’s very versatile!

By default, you’ll generally use an ArrayDeque. That class offers a few functions that let you use it as a queue:

• add(element) adds an element to the back of the queue.
• remove() removes an element from the front of the queue and returns it.
• peek() returns the font element without removing it, or null if the stack is empty.

Alternative Functions

Deque can be used as a stack or a queue, so it has many functions, which can be confusing.

I suggest reading through the Deque JavaDocs. You don’t need to memorize these implementation details, but mentioning that you remember there are alternatives might score you some bonus points.

The Deque class also contains functions that let it work as a stack. For more info, see the stacks tutorial.

Algorithmic Complexity

The power of Deque implementations come from the fact that add(element), remove(), and peek() (and their equivalents in the Deque interface) are very efficient. They’re all constant time O(1).

Example: Queue and ArrayDeque

This short example adds three animals to a queue, and then removes them and prints them out.

Queue<String> queue = new ArrayDeque<>();
queue.add("cats");
queue.add("dogs");
queue.add("lizards");

while(!queue.isEmpty()) {
  String animal = queue.remove();
  System.out.println(animal);
}

Because queues are first-in-first-out, the animals are printed in the same order they’re added.

PriorityQueue

Queues, more specifically the Queue and Deque interfaces and the ArrayDeque class, are handy by themselves. Anytime you need to maintain a list and continuously add to one end and remove from the other, chances are a queue can help you.

But there’s a whole category of technical interview questions the boil down to using a PriorityQueue.

PriorityQueue is a special implementation of the Queue interface that contains the same add() and remove() functions, but has a special property: it keeps its elements sorted!

(This is also called a heap data structure.)

Algorithmic Complexity

Because PriorityQueue maintains the sort order of its elements, its functions have slightly different algorithmic complexities than a typical queue:

• add(element) takes O(log n) time
• remove() also takes O(log n) time
• peek() is still O(1) constant time

Example: Kth Element

Let’s say you want to define a function that takes an array of integers, and an index k, and returns the kth largest element in the array.

You could do this by sorting the array:

public int findKthLargest(int[] nums, int k) {
  Arrays.sort(nums);
  return nums[nums.length - k];
}

The algorithmic complexity is all in the Arrays.sort() function, which is O(n log n).

Can you do better?

Instead of sorting all n elements, you only need to maintain k elements.

You can use a PriorityQueue to maintain those k elements:

public int findKthLargest(int[] nums, int k) {
  PriorityQueue<Integer> priorityQueue = new PriorityQueue();

  // Add the first k elements to the PriorityQueue
  // After this loop, the front of the queue is the kth largest element so far
  for (int i = 0; i < k; i++) {
    priorityQueue.add(nums[i]);
  }

  // Iterate over the rest of the elements in the array
  for (int i = k; i < nums.length; i++) {
    // If the number is bigger than than the kth largest
    // then add it to the PriorityQueue and remove the smallest
    if (nums[i] > priorityQueue.peek()) {
      priorityQueue.remove();
      priorityQueue.add(nums[i]);
    }
  }

  return priorityQueue.peek();
}

Now instead of sorting the entire array, the code maintains a PriorityQueue of size k. The new algorithmic complexity is O(n log k). This is an improvement, as long as k is smaller than n.

There is an even more “optimal” solution to this problem involving an algorithm called quickselect. But the point is, you should include PriorityQueue in your list of algorithms to consider when you’re approaching a problem!

Practice Questions

• Kth Largest Element in an Array
• Find the Winner of the Circular Game
• Number of Students Unable to Eat Lunch
• Remove Duplicate Letters
• Number of Recent Calls
• Find Median from Data Stream

Previous:

Stacks

Next:

Recursion