One of the most fundamental and widely used data structures is the queue. In this blog post, we’ll explore the basics of the queue data structure, its implementation, and some examples of how it can be used to solve common data structure and algorithm problems.

What is a Queue?

A queue is a linear data structure that follows the First-In-First-Out (FIFO) principle, meaning that the first element added to the queue is the first one to be removed. A queue can be thought of as a line of people waiting for a service, where people are added to the end of the line and served from the front of the line.

A queue typically has two primary operations:

1. Enqueue: Adding an element to the end of the queue.
2. Dequeue: Removing an element from the front of the queue.

Additionally, queues often support other operations such as:

• Front: Returns the element at the front of the queue without removing it.
• IsEmpty: Checks if the queue is empty.
• Size: Returns the number of elements in the queue.

How is a Queue Implemented?

There are several ways to implement a queue, including:

1. Array-based implementation: Using an array to store the elements, with a fixed capacity.
2. Linked list implementation: Using a linked list to store the elements, allowing for dynamic resizing.
3. Dynamic array implementation: Using a dynamic array to store the elements, which can resize as needed.

struct Queue<T> {
    private var elements: [T] = []

    mutating func enqueue(_ element: T) {
        elements.append(element)
    }

    mutating func dequeue() -> T? {
        guard !elements.isEmpty else {
            return nil
        }
        return elements.removeFirst()
    }

    func front() -> T? {
        return elements.first
    }

    var isEmpty: Bool {
        return elements.isEmpty
    }

    var size: Int {
        return elements.count
    }
}

Example: Breadth-First Search using a Queue

One common application of queues is in breadth-first search (BFS) algorithms. BFS is used to traverse or search a graph or tree in a level-by-level manner. Here’s an example of how to use a queue to perform BFS on a graph in Swift:

func bfs(graph: [Int: [Int]], startNode: Int) {
    var queue = Queue<Int>()
    var visited = Set<Int>()

    queue.enqueue(startNode)
    visited.insert(startNode)

    while !queue.isEmpty {
        guard let currentNode = queue.dequeue() else {
            break
        }
        print("Visited node: \(currentNode)")

        for neighbor in graph[currentNode] ?? [] {
            if !visited.contains(neighbor) {
                queue.enqueue(neighbor)
                visited.insert(neighbor)
            }
        }
    }
}

// Example usage
let graph = [
    0: [1, 2],
    1: [0, 3, 4],
    2: [0, 5],
    3: [1],
    4: [1, 5],
    5: [2, 4]
]

bfs(graph: graph, startNode: 0)

In this example, we define a bfs function that takes an adjacency list representation of a graph and a starting node. We create a queue to store the nodes to be visited and a set to keep track of visited nodes. We start by enqueueing the starting node and marking it as visited.

Then, we enter a loop that continues until the queue is empty. In each iteration, we dequeue a node, print it as visited, and enqueue its unvisited neighbors. This process ensures that we visit the nodes in a breadth-first manner.

The output of running bfs(graph: graph, startNode: 0) will be:

Visited node: 0
Visited node: 1
Visited node: 2
Visited node: 3
Visited node: 4
Visited node: 5

This demonstrates how the nodes are visited level by level, starting from the starting node.