Table of contents
- What is Queue?
- Queue using Python List - no size limit
- Queue using Python List - no size limit , operations (enqueue, dequeue, peek)
- Circular Queue - Python List, operations (enqueue, dequeue, peek, delete)
- Queue - Linked List, Operations (Create, Enqueue)
- Queue - Linked List, Operations (Dequeue(), isEmpty, Peek)
Welcome to Queue blog!
What is Queue?
Queue is similar as real life queue. In python, queue is a data structure that store items in a first in/first out system. In queue, we follow the FIFO method.
Queue example : Receiving orders, Printer queue, Call center application etc.
Queue using Python List - no size limit
We can implement ques in two ways - Python List, Linked List.
Python List
- Queue without capacity
- Queue with capacity (Circular queue)
Linked List
In case of creating a queue:
Using python list (without capacity), we initialize an empty python list. Then we insert elements into the list. In queue, insertion is known as Enqueue.
In case of removing :
Removing is known as dequeue. If we call dequeue method, it will return the first element of the queue, the element will be removed from the queue also. (you can not run dequeue operation on empty list)
Peek operation :
This method will always return the first element no matter how many time you run it. It will give different result only if you modify the queue list.
isEmpty : Checks if the queue is empty of not.
isFull : Checks if the queue is up to its maximum capacity.
Queue using Python List - no size limit , operations (enqueue, dequeue, peek)
class Queue:
def __init__(self):
self.items = []
def __str__(self):
values = [str(x) for x in self.items]
return ' '.join(values)
def isEmpty(self):
if self.items == []:
return True
return False
def enqueue(self, value): #On^c time complexity
self.items.append(value)
return "Element inserted at the end of the queue"
def dequeue(self):
if self.isEmpty():
return "No element"
return self.items.pop(0) #index of 1st element
def peek(self):
if self.isEmpty():
return "No element in the queue"
return self.items(0)
def delete(self):
self.items = None
customQueue = Queue()
print(customQueue.isEmpty())
customQueue.enqueue(2)
print(customQueue)
Circular Queue - Python List, operations (enqueue, dequeue, peek, delete)
A circular queue is a data structure that uses a singles, fixed size buffer as if it is connected end-to-end. This is efficient when you want to uses a fixed size memory.
Explanation:
start and top refers to specific position/pointers. Generally, start means the beginning of a data structure. In queue, it is the position from where elements are dequeued (deques from the start). On the other hand, top represents the position where an element has been recently add.
class Queue:
def __init__(self, maxSize):
self.items = maxSize = [None]
self.maxSize = maxSize
self.start = -1
self.top = -1
def __str__(self):
values = [str(x) for x in self.items]
return ' '.join(values)
def isFull(self):
if self.top + 1 == self.start:
return True
elif self.start == 0 and self.top + 1 == self.maxSize:
return True
else:
return False
def isEmpty(self):
if self.top == -1:
return True
else:
return False
def enqueue(self,value):
if self.isFull():
return "Queue is full"
else:
if self.top + 1 == self.maxSize:
self.top = 0
else:
self.top += 1
if self.start == -1:
self.start = 0
self.items[self.top] = value
return "The element is inserted at the end of the queue"
def dequeue(self):
if self.isEmpty():
return "There is not any element in the queue"
else:
firstElement = self.items[self.start]
start = self.start
if self.start == self.top:
self.start = -1
self.top = -1
elif self.start + 1 == self.maxSize:
self.start = 0
else:
self.start += 1
self.items[start] = None
return firstElement
def peek(self):
if self.isEmpty():
return "There is not any element in the queue"
else:
return self.items[self.start]
def delete(self):
self.items = self.maxSize = [None]
self.top = -1
self.start = -1
customQueue = Queue(3)
print(customQueue.isFull())
customQueue.enqueue(3)
print(customQueue)
print(customQueue.isFull())
print(customQueue.dequeue())
print(customQueue)
print(customQueue.peek())
print(customQueue.delete())
print(customQueue)
For init method - We are just updating, initializing the variables. Hence, the time complexity is O(N). If the max size is N, The space complexity will be O(N). Everything else has O(1) time and space complexity.
Queue - Linked List, Operations (Create, Enqueue)
Code:
class Node:
def __init__(self, value = None):
self.value = value
self.next = None
def __str(self):
return str(self.value)
class LinkedList:
def __init__(self):
self.head = None
self.tail = None
def __iter__ (self):
curNode = self.head
while curNode:
yield curNode:
curNode = curNode.next
class Queue :
def __init__(self):
self.linkedList = LinkedList()
def __str__(self):
values = [str(x) for x in self.linkedList]
return ' '.join(values)
def enqueue(self, value):
newNode = Node(value)
if self.linkedList == None:
self.linkedList.head = newNode
self.linkedList.tail = newNode
else:
self.linkedList.tail.next = newNode
self.linkedList.tail = newNode
custQueue = Queue()
custQueue.enqueue(1)
custQueue.enqueue(2)
custQueue.enqueue(3)
print(custQueue)
Explanation:
First, we will create a Node class. Then, we will add the __str__ function (a standard function in Python) to make the nodes printable. With this, our node class is finished.
Next, the linked list class. After setting head and tail, we will make the list inerrable because without iterating, we cannot printout the queue. In the __iter__ function, we are just iterating through the linked list yielding the values of nodes in one list.
Now, we will create our queue class. Inside __init__ function of this queue class, we need to initialize an object of the LinkedList over here (the object of LinkedList).
Queue - Linked List, Operations (Dequeue(), isEmpty, Peek)
We are going to add some other methods here also. It's the extension of the previous linked link class.
Code:
def isEmpty(self):
if self.linkedList.head == None:
return True
else:
return False.
def dequeue(self):
if self.isEmpty():
return "No elements"
else:
tempNode = self.linkedList.head
if self.linkedList.head == self.linkedList.tail:
self.linkedList.head = None
self.linkedList.tail = None
else:
self.linkedList.head = self.linkedList.head.next
return tempNode
def peek(self):
if self.isEmpty():
return "No elements in the list"
else:
return self.linkedList.head
def delete(self):
self.linkedList.head = None
self.linkedList.tail = None
print(custQueue.dequeue())
print(custQueue)
print(custQueue.peek())
print(custQueue)
Explanation:
We will use the isEmpty() method in the dequeue method, so I initialized it first. To check if there's any element in the list, we check the head reference. If the head reference is none, there are no elements in the linked list.
Now let's continue to dequeue method. When we dequeue an element, we need to return the first element and remove it from the queue. If there are elements in the queue, we will proceed by making a temp Node which will take the value of the head and will return the value. Then we will do the rest following the if-else condition.
Now we will develop the peek method. Peek method is used for returning the first element from the queue. We are not updating, modifying anything. We are simply returning the first element.
To delete, we just need to update the head, tail reference to None.
Everything here has O(1) time and space complexity.