Computer Science (9645) | Queues

Welcome to the World of Queues!

Hello there! This chapter is all about Queues, one of the most fundamental and useful data structures in computer science. If you can handle waiting in line for a bus or a coffee, you already understand the core concept of a Queue!

Queues are essential because they manage processes and data flow in a highly controlled, ordered way. We will explore how they work, the specific rules they follow, and how we can implement them efficiently in code, tackling some common implementation challenges along the way.

3.2.3 Understanding the Queue Data Structure

The Core Principle: FIFO (First-In, First-Out)

The most important rule for a queue is its policy: FIFO, which stands for First-In, First-Out.

Analogy: Think of a queue at a supermarket. The person who joins the line first is the first person to be served and leave the line. New items (people) always join the back, and items are always removed from the front.

This strict ordering mechanism is what defines a queue and differentiates it from other structures like Stacks (which are Last-In, First-Out).

Key Takeaway: The FIFO Rule

The order in which data enters the queue is the exact order in which it will leave the queue.

The Fundamental Queue Operations

A queue requires specific methods (operations) to manage its contents. When dealing with queues, we use special terminology for adding and removing data.

1. Enqueue (Adding an Item)

Enqueue is the operation used to add an item to the queue.

• Where does the item go? It is always added to the Rear (or Back) of the queue.
• In implementation terms, this often involves updating a pointer or index, usually called the Rear pointer, to point to the new last element.

2. Dequeue (Removing an Item)

Dequeue is the operation used to remove an item from the queue.

• Where is the item removed from? It is always removed from the Front of the queue.
• The Dequeue operation returns the value of the item being removed.
• In implementation terms, this involves updating the Front pointer to point to the new first element in the queue.

Common Mistake Alert: Students often confuse the terminology. Remember: "E" for Enqueue (Enter) at the rear, and "D" for Dequeue (Depart) from the front.

Describing Appropriate Use Cases for Queues

Queues are used whenever resources must be processed fairly and sequentially, ensuring that no request is neglected or delayed indefinitely.

You need a queue data structure when:

• Task Scheduling: Operating Systems (OS) manage multiple tasks or processes waiting for the CPU. A queue ensures that the first task to request CPU time is the next to receive it.
• Input/Output Buffering: When data is transmitted (e.g., streaming video or sending files to a printer), it is stored in a buffer (a queue) to handle differences in processing speed. The data must be processed in the exact order it arrived.
• Simulation: Modelling real-world systems like traffic flow, customer service lines, or manufacturing assembly lines.

Did You Know?

The concept of a "print queue" is a perfect software application of a queue data structure. The first document sent to the printer is the first document printed.

Implementing Queues using One-Dimensional Arrays

While some programming languages offer built-in Queue libraries (and you should have experience using them!), it is vital to understand how queues are built from scratch, typically using a one-dimensional array.

We use two main pointers (or indices) to manage the queue within the array:

• Front: Points to the first item (where the next Dequeue will happen).
• Rear: Points to the last item (where the next Enqueue will happen).

The Linear Queue Implementation

In a simple linear queue, when you enqueue, the Rear pointer moves up by 1. When you dequeue, the Front pointer moves up by 1.

The Problem with Linear Queues:

Imagine an array of size 5. If we add 5 items (filling the array) and then remove 4 items, the Front pointer is now at index 4, and the Rear pointer is at index 5. The first four slots (indexes 0 to 3) are now empty, but we cannot add new items because the Rear pointer has reached the end of the array. This is inefficient as it leads to wasted space at the start of the array.

The Solution: The Circular Queue

The circular queue solves the linear queue problem by allowing the pointers (Front and Rear) to "wrap around" to the start of the array once they reach the end.

Analogy: Imagine the array is a donut or a ring. When the Rear pointer gets to the last slice, the next slice is the first slice again (if it's empty).

How Circular Queues Work (The Wrap-Around)

To make a pointer wrap around, we typically use the MODULO (MOD) operator.

If the array size is \(N\), then when updating a pointer (let's call it P):

New \(P\) = (\(P\) + 1) MOD \(N\)

If \(N\) = 10, and Rear is at index 9, (9 + 1) MOD 10 = 0. The pointer wraps back to index 0. This maximizes the use of the fixed array space.

Testing Queue Status: Empty or Full?

When using an array implementation (whether linear or circular), we must always check the status of the queue before performing an operation to avoid errors (like trying to dequeue from an empty queue).

1. Testing if the Queue is Empty

A queue is empty if the Front and Rear pointers point to the same location, indicating no elements are stored between them.

• Rule for Empty: The queue is empty when Front = Rear.
• Note: Sometimes, when the queue is initialized, Front and Rear are set to a sentinel value like -1 or 0, but the primary indicator of emptiness after use is when they meet up again.

2. Testing if the Queue is Full (Crucial for Circular Arrays)

Determining if a circular queue is full is more challenging because Front = Rear is also the condition for Empty. To distinguish between Full and Empty, array implementations often reserve one slot that is permanently unused.

The queue is considered full when the next position of the Rear pointer is the Front pointer.

• Rule for Full: The queue is full when (Rear + 1) MOD N = Front (where N is the array size).

This rule ensures there is always at least one empty space between Front and Rear, allowing the algorithm to correctly identify whether the queue contains zero items or is completely full.

Don't worry if the circular queue mathematics seem tricky at first. Practice tracing the pointers using a small example array (size 5 or 6), paying close attention to what happens when you hit the highest index, and the MOD operator will start to make sense!

Remember: You should also have experience using the built-in Queue data structures provided by standard programming language libraries, as these handle the complexities of circular allocation and pointer management for you!