Loading lesson path
Concept visual
Start from A
Formula
A queue is a linear data structure that follows the First - In - First - Out (FIFO) principle.Think of a queue as people standing in line in a supermarket. The first person to stand in line is also the first who can pay and leave the supermarket. Basic operations we can do on a queue are:
Adds a new element to the queue.
Removes and returns the first (front) element from the queue.
Returns the first element in the queue. isEmpty: Checks if the queue is empty.
Finds the number of elements in the queue. Queues can be implemented by using arrays or linked lists. Queues can be used to implement job scheduling for an office printer, order processing for e-tickets, or to create algorithms for breadth-first search in graphs. Queues are often mentioned together with Stacks, which is a similar data structure described on the previous page.
For Python lists (and arrays), a Queue can look and behave like this:
Since Python lists has good support for functionality needed to implement queues, we start with creating a queue and do queue operations with just a few lines:
Using a Python list as a queue: queue = [] # Enqueue queue.append('A') queue.append('B') queue.append('C')
print("Queue: ", queue)Formula
# Peek frontElement = queue[0]print("Peek: ", frontElement)Formula
# Dequeue poppedElement = queue.pop(0)print("Dequeue: ", poppedElement)
print("Queue after Dequeue: ", queue)Formula
# isEmpty isEmpty = not bool(queue)print("isEmpty: ", isEmpty)
# Size print("Size: ", len(queue))While using a list is simple, removing elements from the beginning (dequeue operation) requires shifting all remaining elements, making it less efficient for large queues.
Here's a complete implementation of a Queue class:
Using a Python class as a queue: 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)Formula
# Create a queue myQueue = Queue()myQueue.enqueue('A') myQueue.enqueue('B') myQueue.enqueue('C')
print("Queue: ", myQueue.queue)
print("Peek: ", myQueue.peek())
print("Dequeue: ", myQueue.dequeue())
print("Queue after Dequeue: ", myQueue.queue)
print("isEmpty: ", myQueue.isEmpty())
print("Size: ", myQueue.size())A linked list consists of nodes with some sort of data, and a pointer to the next node. A big benefit with using linked lists is that nodes are stored wherever there is free space in memory, the nodes do not have to be stored contiguously right after each other like elements are stored in arrays. Another nice thing with linked lists is that when adding or removing nodes, the rest of the nodes in the list do not have to be shifted. To better understand the benefits with using arrays or linked lists to implement queues, you should check out this page that explains how arrays and linked lists are stored in memory. This is how a queue can be implemented using a linked list.
Creating a Queue using a Linked List: class Node:
def __init__(self, data):Formula
self.data = data self.next = None class Queue:def __init__(self):
self.front = None self.rear = None self.length = 0 def enqueue(self, element):Formula
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"Formula
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):Formula
temp = self.front while temp:print(temp.data, end=" -> ")
temp = temp.next print()Formula
# Create a queue myQueue = Queue()myQueue.enqueue('A') myQueue.enqueue('B') myQueue.enqueue('C')
print("Queue: ", end="")
myQueue.printQueue()
print("Peek: ", myQueue.peek())
print("Dequeue: ", myQueue.dequeue())
print("Queue after Dequeue: ", end="")
myQueue.printQueue()
print("isEmpty: ", myQueue.isEmpty())
print("Size: ", myQueue.size())Reasons for using linked lists to implement queues:
The queue can grow and shrink dynamically, unlike with arrays.
The front element of the queue can be removed (enqueue) without having to shift other elements in the memory. Reasons for not using linked lists to implement queues:
Each queue element must contain the address to the next element (the next linked list node).
The code might be harder to read and write for some because it is longer and more complex.
Formula
Queues are used in many real - world scenarios: