Queue implementation in Python
In this post, you will learn how to implement a Queue using Python programming language.
A queue is a linear data structure where insertion of element is done from one end and deletion from the other end. The queue is like a line of person at polling booth where the first person in the line is first voted. This is called First-In-First-Out (FIFO). Insertion of the element is done from the one end called FRONT end and deletion is done from the other end called REAR.
Queue Operations
These are the operations performed by a queue.
- Enqueue - The element to add in a queue. If the queue is full, then it is said to be an overflow condition.
- Dequeue - The element to delete in a queue. If the queue is empty, then it is said to be an underflow condition.
- Peek - Retrieve the element from the front end of the queue without removing it from the queue.
- IsEmpty - Check if the queue is empty or not.
- Size - Return the total number of elements present in the queue.
- Front - Get the front item from queue.
- Rear - Get the last item from queue.
Algorithm to Insert Element in a Queue
Step 1: IF REAR = MAX-1
print('Queue Overflow')
return
[END OF IF]
Step 2: IF FRONT = -1 and REAR = -1
SET FRONT = REAR = 0
ELSE
SET REAR = REAR + 1
[END OF IF]
Step 3: SET QUEUE[REAR] = NUM
Step 4: EXIT
In the above algorithm, we have checked the existence of space in the queue. If there is no space then print 'Queue Overflow' and the code is exited and if not then, we check the element at the FRONT and REAR, if both are empty then set both to 0 else increase REAR with one and insert element from the REAR end and return.
Algorithm to Delete Element in a Queue
Step 1: IF FRONT = -1 OR FRONT > REAR
print('Queue Underflow')
return
ELSE
SET FRONT = FRONT + 1
[END OF IF]
Step 2: EXIT
In the above algorithm, we have checked the existence of elements in the queue. If there is no any element, then print 'Queue Underflow' and the code is exited and if not, then FRONT is increased by one and point to the next element in the queue.
Queue Implementation in Python
Queue in Python can be implemented in the given ways:
- list
- collections.deque
- queue.Queue
Implementing Queue using List
A list is a sequence of indexed and ordered values that can be used as a queue. Lists are quite slow as the insertion or deletion of an element at the beginning requires shifting all of the other elements by one. It requires O(n) time.
# Initializing a queue
queue = []
# Inserting elements in a queue
queue.append(22)
queue.append(98)
queue.append(55)
queue.append(78)
queue.append(43)
print("Initial Queue :",queue)
# Removing elements from a queue
print(queue.pop(0))
print(queue.pop(0))
print(queue.pop(0))
print("After Removing elements :",queue)
Output of the above code:
Initial Queue : [22, 98, 55, 78, 43]
22
98
55
After Removing elements : [78, 43]
Python implement queue using queue module
We can implement queue in Python using the deque class from the collections module. It is preferred over list in the cases where we need quicker append and pop operations from both the ends of container. It requires O(1) time complexity for append and pop operations.
from collections import deque
queue = deque()
# Inserting elements in a queue
queue.append(99)
queue.append(89)
queue.append(23)
queue.append(18)
print("Initial Queue :",queue)
# Removing elements from a queue
print(queue.popleft())
print(queue.popleft())
print("After Removing elements: ",queue)
Output of the above code:
Initial Queue : deque([99, 89, 23, 18])
99
89
After Removing elements: deque([23, 18])
Python implement queue using queue.Queue
Queue is an in-built module of Python which is basically used to implement a queue.
from queue import Queue
queue = Queue(maxsize=4)
print("Initial Size Before Insertion:",queue.qsize())
queue.put(99)
queue.put(58)
queue.put(91)
queue.put(81)
print("After Insertion:",queue.qsize())
print("Queue is Full or Not:",queue.full())
print("Size of Queue:",queue.qsize())
print("Removing Elements:")
print(queue.get())
print(queue.get())
print(queue.get())
print("Is it empty?",queue.empty())
print(queue.get())
print("Is it empty?",queue.empty())
print("Size of Queue:",queue.qsize())
Related Articles
Convert Python list to numpy arrayConvert string to list Python
Python program to list even and odd numbers of a list
Python loop through list
Sort list in descending order Python
Convert array to list Python
Python take screenshot of specific window
Web scraping Python BeautifulSoup
Check if two strings are anagrams Python
Python program to add two numbers
Print new line python
Python for loop index
Convert List to Dataframe Python
numpy random choice
Dictionary inside list python
Check if list is empty Python
Python raise keyword
Python program to get the largest number from a list
Python program to map two lists into a dictionary