September 17, 2023

tutorial interviewingAt 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.

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.

`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.

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)`

.

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.

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.)

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

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!

- 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

I posted a new article about techniques for using Queue data structures in technical interviews.

Check it out here:

Use Queue data structures in technical interviews.

Happy Coding is a community of folks just like you learning about coding.

Do you have a comment or question? Post it here!

Comments are powered by the Happy Coding forum. This page has a corresponding forum post, and replies to that post show up as comments here. Click the button above to go to the forum to post a comment!