Queues

A queue is an abstract data type that follows the "First In, First Out" (FIFO) principle. This means the first item added to the queue is the first item to be removed.

Imagine a line of people waiting for a movie theater ticket. The first person to get in line is the first to be served and leave. No one typically cuts in the middle or leaves from the middle unless all the people before have been served. This orderly process is the essence of FIFO.

Key Operations

Here are the three primary operations you can perform on a queue data structure:

Enqueue

• In queue terminology, enqueueing is the act of adding an element to the back of the queue. Just as a new person joins the end of the line, adding an element in a data context places a data element (like a number, character, or object) at the end of the queue.
• This operation is accomplished in constant time, O(1), because it doesn't require shifting or moving other elements around; you simply add the new item to the end.

Dequeue

• Similar to the first person in line being served and leaving the queue, dequeueing in a queue data structure involves removing the front element.
• This is also a constant time operation, O(1), as it directly accesses the front element without needing to rearrange or look through the rest of the queue.

Peek

• In a queue of people, you might look at the person at the front to see who will be served next. In a queue data structure, "peeking" allows you to see the value of the front element without removing it from the queue. This can be useful for checking the value before deciding to serve or remove it.

---

Practical Applications of Queues

Process Scheduling

In operating systems, processes are managed in a queue format. Each process joins the queue and waits its turn to be executed by the CPU. The first process added to the queue is the first to get CPU time, ensuring orderly processing.

Print Job Management

Consider a printer connected to multiple computers. Print jobs sent to the printer are managed using a queue, ensuring that documents are printed in the order they were received. This prevents conflicts and confusion, maintaining a fair system.

Real-Time Systems

In real-time systems like traffic lights or customer service lines, queues manage tasks that must be executed in the order they arrive. This can ensure fairness and efficiency, reducing wait times and preventing bottlenecks.

Breadth-First Search (BFS) in Graphs

We will cover Graphs in one of the later lessons. For now, know that a breadth-first search algorithm exists that uses a queue to systematically explore each vertex (node of a graph) and its neighbors.

In the next assignment, we'll see how we can implement a queue using a linked list.