Unraveling the Queue: A Fundamental Data Structure
Introduction
A queue is an ordered collection of items where the addition of new items is allowed at one end but the removal occurs at the opposite end. The piece that has been in the queue the longest will be deleted first. This data format is utilized in a variety of applications, such as computer networks, operating systems, and data processing. The end where new items are added is known as the “rear” of the queue. The end where items are removed from the queue is known as the “front.”
Queues follow an ordering principle called FIFO, first-in-first-out.
Meaning the oldest (first) added item will be the first to be removed. The most recently added item in the queue is removed last.
Basics of a Queue
A queue has two primary operations: enqueue and dequeue.
- Enqueue: This operation adds an element to the end of the queue.
- Dequeue: This operation removes an element from the front of the queue.
- Peek/Top: This operation helps to get the value of the front of the queue without removing it.
- isFull: This operation checks if the queue is full.
- isEmpty: This operation checks if the queue is empty.
- Size: This operation returns the total items present in the queue.
Types of Queues
There are various types of queues, each serving a different purpose:
1. Simple Queue: A standard queue where enqueue and dequeue operations are performed at the rear and front, respectively.
2. Circular Queue: A more complex type where the last element points back to the first element making a circle of elements.
3. Priority Queue: Elements are assigned priorities. When accessing elements, the element with the highest priority is dequeued first.
4. Dequeue (Double Ended Queue): In this variant, insertion and removal of elements can be performed from either the front or rear.
Advantages and Disadvantages
Queues offer several advantages. They are simple and intuitive to use, and their FIFO nature can model several real-world processes. However, they are not without disadvantages. For instance, a simple queue does not offer flexibility in terms of data access — you can only access the data from the front of the queue.
Real-Life Applications
Queues are prevalent in computing systems. For example, print jobs are managed in a queue, with the first job printed first. In computer networks, routers manage data packets in a queue, and in operating systems, processes, and resources are scheduled using queues. Even in our daily life, several scenarios follow the queue data structure, like people standing in a line to order food.
The Grand Central Dispatch (GCD) framework in iOS is an excellent real-world example of queues being used to handle concurrent tasks. GCD works by allowing you to execute tasks according to their importance and resources. Tasks, which can be either data computation or more commonly IO, such as reading and writing to a database, are put in a queue.
The queue used by GCD is a type of priority queue. When tasks enter the queue, they’re not necessarily completed in a strict FIFO order. Instead, each task is assigned a priority level (user-interactive, user-initiated, utility, or background), and GCD manages the execution of tasks based on their priority [1]. This means tasks critical to the user experience, like UI updates, can be executed before less critical tasks, like writing logs to disk.
The beauty of GCD is that it abstracts the complexities of thread management and provides a simple interface to work with tasks concurrently. It automatically manages the pool of threads and executes tasks in parallel wherever possible, considering the current system load and available cores [2].
It’s important to note that while GCD uses queues, it doesn’t strictly follow the FIFO order. However, it does maintain order within each priority level. This design highlights the versatility of the queue data structure and its applicability in managing tasks and resources efficiently.
Code Implementation
Let’s look at a simple implementation of a queue in Python:
In this code, we define a `Queue` class with an empty list. The `enqueue` method appends an item to the end of the list, representing adding an element to the rear of the queue. The `dequeue` method pops the first element from the list, representing the removal of the front element of the queue. The `display` method returns the current state of the queue.
Conclusion
The queue data structure, with its simplicity and versatility, is a fundamental building block in computer science. Understanding its operations and the various types can help in designing efficient algorithms and systems.
References
[1] Apple Inc. “Dispatch Queues.” Apple Developer Documentation. (https://developer.apple.com/documentation/dispatch/dispatchqueue)
[2] Vandad Nahavandipoor. “Concurrent Programming with Grand Central Dispatch.” O’Reilly Media, Inc., 2015.
[3] Besher Al Maleh. “Concurrency Explained: How to Build a Multi-Threaded iOS App” FreeCodeCamp, 2020. https://www.freecodecamp.org/news/ios-concurrency/
[3] “Queue Data Structure” GeeksForGeeks, 2023. https://www.geeksforgeeks.org/queue-data-structure/