Queue Implementation in Python
This article covers queue implementation in Python. A queue is a linear data structure that follows the FIFO (First–In, First–Out) order, i.e., the item inserted first will be the first one out.
A queue supports the following standard operations:
- enqueue: Inserts an element at the rear (right side) of the queue.
- dequeue: Removes the element from the front (left side) of the queue and returns it.
- peek: Returns the element at the front of the queue without removing it.
- isEmpty: Checks whether the queue is empty.
- size: Returns the total number of elements present in the queue.
The time complexity of all the above operations should be constant.
Queue Implementation using a List:
The queue can easily be implemented as a list. Following is the custom queue implementation in Python, which uses a list:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 |
# Custom queue implementation in Python class Queue: # Initialize queue def __init__(self, size=1000): self.q = [None] * size # list to store queue elements self.capacity = size # maximum capacity of the queue self.front = 0 # front points to the front element in the queue self.rear = -1 # rear points to the last element in the queue self.count = 0 # current size of the queue # Function to dequeue the front element def dequeue(self): # check for queue underflow if self.isEmpty(): print('Queue Underflow!! Terminating process.') exit(-1) x = self.q[self.front] print('Removing element…', x) self.front = (self.front + 1) % self.capacity self.count = self.count - 1 return x # Function to add an element to the queue def enqueue(self, value): # check for queue overflow if self.isFull(): print('Overflow!! Terminating process.') exit(-1) print('Inserting element…', value) self.rear = (self.rear + 1) % self.capacity self.q[self.rear] = value self.count = self.count + 1 # Function to return the front element of the queue def peek(self): if self.isEmpty(): print('Queue UnderFlow!! Terminating process.') exit(-1) return self.q[self.front] # Function to return the size of the queue def size(self): return self.count # Function to check if the queue is empty or not def isEmpty(self): return self.size() == 0 # Function to check if the queue is full or not def isFull(self): return self.size() == self.capacity if __name__ == '__main__': # create a queue of capacity 5 q = Queue(5) q.enqueue(1) q.enqueue(2) q.enqueue(3) print('The queue size is', q.size()) print('The front element is', q.peek()) q.dequeue() print('The front element is', q.peek()) q.dequeue() q.dequeue() if q.isEmpty(): print('The queue is empty') else: print('The queue is not empty') |
Output:
Inserting 1
Inserting 2
Inserting 3
The front element is 1
Removing 1
The front element is 2
The queue size is 2
Removing 2
Removing 3
The queue is empty
Using deque():
Python’s library offers a deque object, which stands for the double-ended queue. A deque is a generalization of stack and queues which support constant-time insertions and removals from either side of the deque in either direction.
Following is a simple example demonstrating the usage of deque to implement queue data structure in Python:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 |
from collections import deque # Program to demonstrate queue in Python if __name__ == '__main__': queue = deque() queue.append(1) # Insert 1 into the queue queue.append(2) # Insert 2 into the queue queue.append(3) # Insert 3 into the queue queue.append(4) # Insert 4 into the queue # Print front item of the queue print('The front element is', queue[0]) # 1 queue.popleft() # removing the front element (1) queue.popleft() # removing the front element (2) # Print front item of the queue print('The front element is', queue[0]) # 3 # Print the number of elements present in the queue print('The queue size is', len(queue)) # 2 # check whether the queue is empty if len(queue) == 0: print('The queue is empty') else: print('The queue is not empty') |
Output:
The front element is 1
The front element is 3
The queue size is 2
The queue is not empty
Also See:
Queue Implementation using a Linked List – C, Java, and Python
Thanks for reading.
To share your code in the comments, please use our online compiler that supports C, C++, Java, Python, JavaScript, C#, PHP, and many more popular programming languages.
Like us? Refer us to your friends and support our growth. Happy coding :)