DSA Queues
Queues
A data structure with a large capacity is a queue.
=== EXAMPLE MUKAVU ====
Imagine a queue as a group of individuals waiting in a grocery line.
The first individual to pay and exit the store is also the first one to get in line. First In First Out, or FIFO, is the name given to this method of grouping elements.
The fundamental tasks we can perform on a queue are:
- Enqueue: Introduces a fresh component into the queue.
- Dequeue: Takes the front element out of the queue and puts it back.
- Peek: Provides the queue’s initial element back.
- isEmpty: Determines whether the queue is empty.
- Size: Determines how many items are in the queue.
Try out these fundamental functions in the queue animation above.
One way to implement queues is with linked lists or arrays.
Queues can be used to construct algorithms for breadth-first search in graphs, schedule jobs for an office printer, and handle orders for e-tickets.
It’s common to hear about queues in conjunction with stacks, another comparable data structure covered on the preceding page.
Queue Implementation using Arrays
You should read this page, which describes how arrays and linked lists are stored in memory, in order to gain a better understanding of the advantages of using them to create queues.
This is the appearance of using an array as a queue:
=== EXAMPLE MUKAVU ====
Reasons to use arrays while implementing queues:
- Memory Efficient: Unlike linked list nodes, array elements do not store the address of the subsequent element.
- Easier to implement and comprehend: Implementing queues with arrays requires less code than with linked lists, and as a result, it’s usually easier to comprehend as well.
Reasons for avoiding implementing queues with arrays:
- Fixed size: An array takes up a predetermined amount of memory. This implies that it might use more memory than is necessary or that it won’t be able to accommodate more elements if the array gets full. Moreover, scaling an array may be expensive.
- Shifting cost: When an element is dequeued, the first element in the queue is deleted, requiring the other elements to be shifted to make room for the removed elements. This is ineffective and may lead to issues, particularly in the event of a lengthy line.
- Other options: Data structures that are pre-built and better suited for queue operations than arrays can be found in some computer languages.
Note: Although the Python ‘list’ data type is actually utilized for arrays in this tutorial, it can be used in the same manner as arrays for the purposes of this guide. Find out more about lists in Python here.
We begin by building a queue and perform queue operations with just a few lines of code because Python lists provide decent support for the functionality required to implement queues:
Example
Python:
queue = []
# Enqueue
queue.append('A')
queue.append('B')
queue.append('C')
print("Queue: ", queue)
# Dequeue
element = queue.pop(0)
print("Dequeue: ", element)
# Peek
frontElement = queue[0]
print("Peek: ", frontElement)
# isEmpty
isEmpty = not bool(queue)
print("isEmpty: ", isEmpty)
# Size
print("Size: ", len(queue))
However, we should establish a queue class in order to explicitly create a data structure for queues that includes the fundamental functions. Python queue creation is also more akin to queue creation in other computer languages, such as C and Java.
Example
Python:
class Queue:
def __init__(self):
self.queue = []
def enqueue(self, element):
self.queue.append(element)
def dequeue(self):
if self.isEmpty():
return "Queue is empty"
return self.queue.pop(0)
def peek(self):
if self.isEmpty():
return "Queue is empty"
return self.queue[0]
def isEmpty(self):
return len(self.queue) == 0
def size(self):
return len(self.queue)
# Create a queue
myQueue = Queue()
myQueue.enqueue('A')
myQueue.enqueue('B')
myQueue.enqueue('C')
print("Queue: ", myQueue.queue)
print("Dequeue: ", myQueue.dequeue())
print("Peek: ", myQueue.peek())
print("isEmpty: ", myQueue.isEmpty())
print("Size: ", myQueue.size())
Queue Implementation using Linked Lists
Reasons for implementing queues with linked lists:
- Dynamic size: Unlike arrays, the queue can expand and contract on a whim.
- No shifting: It is possible to remove (enqueue) the front member of the queue without moving the other memory components.
Reasons against implementing queues using linked lists:
- Additional memory: The address of the subsequent element (the subsequent linked list node) must be contained in each queue element.
- Readability: Because the code is longer and more complex, some people may find it more difficult to understand and write.
This is the linked list implementation of a queue.
Example
Python:
class Node:
def __init__(self, data):
self.data = data
self.next = None
class Queue:
def __init__(self):
self.front = None
self.rear = None
self.length = 0
def enqueue(self, element):
new_node = Node(element)
if self.rear is None:
self.front = self.rear = new_node
self.length += 1
return
self.rear.next = new_node
self.rear = new_node
self.length += 1
def dequeue(self):
if self.isEmpty():
return "Queue is empty"
temp = self.front
self.front = temp.next
self.length -= 1
if self.front is None:
self.rear = None
return temp.data
def peek(self):
if self.isEmpty():
return "Queue is empty"
return self.front.data
def isEmpty(self):
return self.length == 0
def size(self):
return self.length
def printQueue(self):
temp = self.front
while temp:
print(temp.data, end=" ")
temp = temp.next
print()
# Create a queue
myQueue = Queue()
myQueue.enqueue('A')
myQueue.enqueue('B')
myQueue.enqueue('C')
print("Queue: ", end="")
myQueue.printQueue()
print("Dequeue: ", myQueue.dequeue())
print("Peek: ", myQueue.peek())
print("isEmpty: ", myQueue.isEmpty())
print("Size: ", myQueue.size())
