Queues In Data Structure
A fundamental data structure that is used in many software applications, queues in data structure are arranged according to the “first-in, first-out” (FIFO) concept. Accordingly, the item that is taken out of the queue or served first will be the one that was added first. A queue is sometimes compared to a queue of people waiting in the real world, where those at the front are served first and newcomers join at the back.
Ideas and Terminologies The “back” or “rear” end of a queue is where elements are put, and the “front” or “head” end is where they are withdrawn, in contrast to stacks, which follow the Last-In, First-Out (LIFO) concept. The operation of the queue depends on this restricted access pattern.
Core Operations of a Queue ADT
The Abstract Data Type (ADT) queue offers a number of basic methods
- The function enqueue(e) places element e at the back of the queue.
- Dequeue(): Takes the element at the front of the queue and returns it. If the queue is empty, there is an error.
- Without deleting the element at the front of the queue, first() or peek() returns a reference to it. If the queue is empty, there is an error.
- If the queue is empty, the function is_empty() or isEmpty() returns True.
- Size() or len(Q): Gives the number of items in the queue.
- The is_full() function is used in array-based implementations to determine whether the underlying storage of the queue is full.
Implementations Queue In Array
Implementation using a Python List
Python List Implementation (Array-Based) To implement a queue with a Python list, a simple but ineffective method is to use pop(0) for dequeuing and append(e) for enqueuing. But because pop(0) necessitates moving every last element to the left, it is extremely inefficient and has an O(N) time complexity, where N is the number of elements in the list.
A circular array is used in an array-based approach that is more reliable and effective. This entails keeping the head (or front) and tail (or rear) pointers (indices) intact and letting the contents of the queues in data structure “wrap around” the array’s ends. The element at head is eliminated when dequeue is called, and head is then increased circularly using the modulo operator (f = (f + 1) % N). The size is increased and the new element is added to the queue at avail = (front + size) % len(data). By using this method, the front of the queues in data structure doesn’t keep moving to the right and wasting room.
An implementation of an array-based queue is shown here:
Example:
class QueueList:
def __init__(self):
self.queue = []
def enqueue(self, item):
self.queue.append(item)
print(f"Enqueued: {item}")
def dequeue(self):
if not self.is_empty():
item = self.queue.pop(0)
print(f"Dequeued: {item}")
return item
print("Queue is empty!")
return None
def peek(self):
if not self.is_empty():
return self.queue[0]
print("Queue is empty!")
return None
def is_empty(self):
return len(self.queue) == 0
def display(self):
print("Queue:", self.queue)
# Example Usage
queue = QueueList()
queue.enqueue(1)
queue.enqueue(2)
queue.enqueue(3)
queue.display()
queue.dequeue()
queue.peek()
queue.display()Output:
Enqueued: 1
Enqueued: 2
Enqueued: 3
Queue: [1, 2, 3]
Dequeued: 1
Queue: [2, 3]This array-based queue implementation provides O(1) time for first, is_empty, and len as well as amortised O(1) time for enqueue and dequeue operations (because of sporadic array expansion). It uses an O(N) amount of space.
Implementation using a Linked List
Using a Linked List to Implement When used to create queues in data structure , linked lists work effectively because they are dynamic data structures that can adjust their size as needed, preventing overflow problems unless specifically limited. It is possible to execute operations at the ends of a linked list (deletation at the head, insertion at the tail) effectively in O(1) time. Usually, a linked list queue keeps track of head and tail pointers to make these tasks easier.
- enqueue(e): The tail now has a new node added to it. Both head and tail are occupied by the new node if the queue is empty.
- dequeue(): Gets rid of the element at the top. Additionally, the tail pointer is set to None if the queues in data structure is cleared after deletion.
- first(): merely returns the head node’s data.
The worst-case time for all operations in a linked list implementation of a queue is usually O(1). The present amount of items results in a linear space utilisation. A rotate() method for effective front-to-back element transfer is made possible by the ability of circularly linked lists to construct queues.
Applications of Queues
Uses for Queues In many real-world and computer contexts, queues are utilised extensively.
Operating systems: Operating systems organise data and manage in computers. Desktop computers’ hierarchical file system replicates traditional document storage with a root directory including subdirectories and files, similar to a tree with root nodes, nodes with children, and leaf nodes. These file systems use recursive algorithms for numerous operating system functions, such as copying or removing directories.
Customer Service: Managing client requests at contact centres or on waitlists at dining establishments while making sure they are handled in the order they were received is known as customer service.
Algorithms: Step-by-step techniques to complete a task in a finite period are algorithms. They, together with data structures, dictate what can be computed with available in essential for program efficiency. Knowing algorithms is the foundation of computer science.
Data processing: In data structures and algorithms, data processing organises, manages, and stores data for easier access and modification. A data structure organises and accesses data, while an algorithm performs a task step-by-step in a finite time. Data structures store, relate, and operate on data sets, making them essential for many computer methods. This field characterises algorithm and data structure operation execution times and takes space utilisation into account.
System Simulations: Many computing applications use system simulations to mimic real-world settings and forecast or analyse behaviour. Functions that create random numbers are widely utilised in computer games, cryptography, and simulations. Simulations are used in operating systems to schedule CPU jobs using priority queues. A software can mimic CPU jobs in a loop where each iteration represents a CPU time slice and jobs are assigned priorities and lengths. The CPU processes the highest priority job that runs uninterrupted for its set length.
Special Queues
Priority Queues: Associated “keys” that indicate an element’s priority are stored in priority queues. Whatever the sequence of insertion, the element with the highest priority (e.g., minimal key) is always retrieved first. Heaps are frequently used to effectively implement priority queues.
Double-Ended Queues: Pronounced “deck,” double-ended queues (also known as deques) are more general queue-like structures that support both front-end and back-end insertion and deletion operations. They offer O(1) amortised time for all operations and can be implemented with doubly linked lists or circular arrays.