4.1.5 Using Queues in Computers
Computational Structures
Queues are used to implement Breadth-First Search (BFS) in Graph, Task scheduling, Print Spooling while printing jobs and Call centre systems. Let's discuss them one by one.
4.1.5.1 Breadth-First Search Algorithm (BFS) in Graph
BFS is an algorithm used to explore and traverse data structures like trees or graphs. It systematically examines all the nodes at the present “level” or depth before moving on to nodes at the next level.
Imagine you and your friends are visiting a zoo. The zoo has many animal enclosures connected by paths. You want to see all the animals, so you need a plan to visit every enclosure without missing any. BFS is a method that helps you do this. To follow this method, you will use a queue, which is like a line of people waiting for their turn.
- Start at the Entrance: You begin your visit at the zoo entrance, which is the first enclosure you will explore. This entrance is like the starting point in a map, called the “start node”.
- Using a Queue to Visit Enclosures: To stay organized, you put the entrance in a queue. The queue will help you visit each enclosure in the order you discover them. Think of the queue as a line where you add the enclosures you find so you can visit them one by one.
- Visit the First Enclosure: You start by visiting the first enclosure in the queue (the one at the front of the line). After seeing the animals there, you look at the map to find all the nearby enclosures connected to it. These nearby enclosures are called "neighboring enclosures." You then add (enqueue) these neighboring enclosures to the queue so you can visit them next.