Deep Dive into Queues & LeetCode Practice

Imagine a line in a coffee shop. The first person in line gets served first, right? That’s exactly how a Queue works in data structures.

What are Queues?

A Queue follows the First In First Out (FIFO) principle. Just like in a coffee shop, the first person to get in line is the first one to get served. In programming, we use Queues to manage data in a specific order.

Remember, in Queues, the action happens at both ends!

When to Use Queues?

Queues are vital in programming for tasks like managing requests on a server, handling data in real-time systems, and scenarios where order matters. They ensure that everything gets processed in the right order, maintaining fairness and efficiency.

We use Queues when we need to maintain order and quick access at both ends. They’re perfect for task scheduling, order processing, and breadth-first search in trees or graphs.

Big O Complexities of Queue Operations

Now, let’s decode the performance of Queues.

Queues support primary operations like Enqueue (adding to the back), Dequeue (removing from the front), and Peek (looking at the front item).

const myQueue = new Queue()
myQueue.enqueue(10) 
myQueue.enqueue(20)

myQueue.peek() // Outputs: 10
myQueue.dequeue() // Outputs: 10 
myQueue.peek() // Outputs: 20

These operations are super fast, each with a time complexity of O(1).

However, like any other data structure, Queues have their nuances.

Searching and deleting specific elements in a Queue are O(n) operations, as you might need to traverse the entire Queue. It’s not what Queues are best at, but it’s possible.

let target = 30;
let index = myQueue.indexOf(target);  // Search: O(n)
if (index !== -1) myQueue.splice(index, 1);  // Delete: O(n)

Remember that Queues are mainly used in scenarios where order is important and operations are happening at both ends.

How Are Queues Implemented?

Let’s take a step back and understand how queues are actually implemented under the hood.

Using Arrays

In many programming languages, including JavaScript, you can implement a queue using arrays. Arrays provide a simple and intuitive way to represent a queue. However, there are some nuances to be aware of in terms of performance.

let queue = []
queue.push(1)  // Enqueue: O(1)
queue.push(2)
queue.shift()  // Dequeue: O(n)

While push (enqueue) operations are O(1), shift (dequeue) operations are O(n) because all remaining elements need to be shifted down. If performance is a critical concern, especially for large datasets, this might not be the best choice.

Using Linked Lists

A more efficient way, especially for dequeue operations, is to use a linked list. In a singly linked list, enqueue operations are O(1), and if we maintain a reference to the last node, dequeue operations can also be O(1).

const myQueue = new Queue()
myQueue.enqueue(10)
myQueue.enqueue(20)

myQueue.peek() // Outputs: 10
myQueue.dequeue() // Outputs: 10
myQueue.peek() // Outputs: 20

With this approach, both enqueue and dequeue operations are consistently fast, making it a preferred choice for implementing a queue in scenarios where performance is key.

LeetCode Challenge: Number of Recent Calls (LeetCode 933)

Now that you’ve got a good grasp on queues head over to LeetCode and try solving “Number of Recent Calls” (LeetCode 933). This problem will test your ability to use queues in a real-world scenario.

Write your code to keep track of times of the recent requests, using a queue to efficiently perform the required operations. Remember, you need to return the count of requests in the last 3000 milliseconds for every call to ping.

Think about the time complexity of the ping function and how using a queue can help maintain an efficient solution.

Quick Recap

Queues are FIFO data structures with constant time O(1) operations for adding, removing, and peeking at elements. They are your go-to when order and efficiency matter.

We also have a LIFO data structure which is the opposite of queues. They are called stacks. If you’d like to learn more about them check out my other article about Stacks data structure.