Loading lesson path
Concept visual
Start from A
A queue is a data structure that can hold many elements.
enqueue() dequeue() peek() isEmpty()
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. This way of organizing elements is called FIFO: First In First Out. 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. Experiment with these basic operations in the queue animation above. 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.
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 it looks like when we use an array as a queue: [
]
enqueue() dequeue() peek() isEmpty()
Reasons to implement queues using arrays:
Array elements do not hold the next elements address like linked list nodes do.
Using arrays to implement queues require less code than using linked lists, and for this reason it is typically easier to understand as well. Reasons for not using arrays to implement queues:
An array occupies a fixed part of the memory. This means that it could take up more memory than needed, or if the array fills up, it cannot hold more elements. And resizing an array can be costly.
Dequeue causes the first element in a queue to be removed, and the other elements must be shifted to take the removed elements' place. This is inefficient and can cause problems, especially if the queue is long.
Some programming languages have built-in data structures optimized for queue operations that are better than using arrays.
When using arrays in Python for this tutorial, we are really using the Python 'list' data type, but for the scope of this tutorial the 'list' data type can be used in the same way as an array. Learn more about Python lists here. 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:
queue = []
# Enqueue queue.append('A') queue.append('B') queue.append('C')
print("Queue: ", queue)Formula
# Dequeue element = queue.pop(0)print("Dequeue: ", element)Formula
# Peek frontElement = queue[0]print("Peek: ", frontElement)Formula
# isEmpty isEmpty = not bool(queue)print("isEmpty: ", isEmpty)# Size print("Size: ", len(queue))But to explicitly create a data structure for queues, with basic operations, we should create a queue class instead. This way of creating queues in Python is also more similar to how queues can be created in other programming languages like C and Java.
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) == 0def 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("Dequeue: ", myQueue.dequeue())print("Peek: ", myQueue.peek())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 (dequeue) 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. This is how a queue can be implemented using a linked list.
class Node:
def __init__(self, data):Formula
self.data = data self.next = Noneclass Queue:
def __init__(self):Formula
self.front = None self.rear = None self.length = 0def 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 += 1def 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.datadef peek(self):
if self.isEmpty():
return "Queue is empty"
return self.front.datadef isEmpty(self):
return self.length == 0def size(self):
return self.lengthdef 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("Dequeue: ", myQueue.dequeue())print("Peek: ", myQueue.peek())print("isEmpty: ", myQueue.isEmpty())print("Size: ", myQueue.size())