This Article will help you to understand a Queue data structure and how to implement it.
A Queue is a simple data structure concept that can be easily applied in our day to day life, like when you stand in a line to buy coffee at Starbucks.
Let's make a few observations based on this example:
Now, let’s look at the above points programmatically:
- Queues are open from both ends meaning elements are added from the back and removed from the front
- The element to be added first is removed first (First In First Out - FIFO) If all the elements are removed, then the queue is empty and if you try to remove elements from an empty queue, a warning or an error message is thrown.
- If the queue is full and you add more elements to the queue, a warning or error message must be thrown.
Algorithm
- Declare a list and an integer MaxSize, denoting a virtual maximum size of the Queue
- Head and Tail are initially set to 0
- Size method
- Calculates the number of elements in the queue -> Size = Tail - Head
- Reset method:
- Resets Tail and Head to 0
- Creates a new Queue (initializes queue to a new list)
- Enqueue operation:
- Check if Size is less than the MaxSize:
- If yes, append data to Queue and then increment Tail by 1
- If no, print Queue full message
- Check if Size is less than the MaxSize:
- Dequeue operation:
- Check if Size is greater than 0:
- If yes, pop the first element from the list and increment Head by 1
- If no:
- Call Reset method
- Print Queue empty message
- Check if Size is greater than 0:
class Queue:
#Constructor
def __init__(self):
self.queue = list()
self.maxSize = 8
self.head = 0
self.tail = 0
#Adding elements
def enqueue(self,data):
#Checking if the queue is full
if self.size() >= self.maxSize:
return ("Queue Full")
self.queue.append(data)
self.tail += 1
return True
#Deleting elements
def dequeue(self):
#Checking if the queue is empty
if self.size() <= 0:
self.resetQueue()
return ("Queue Empty")
data = self.queue[self.head]
self.head+=1
return data
#Calculate size
def size(self):
return self.tail - self.head
#Reset queue
def resetQueue(self):
self.tail = 0
self.head = 0
self.queue = list()
q = Queue()
print(q.enqueue(1))#prints True
print(q.enqueue(2))#prints True
print(q.enqueue(3))#prints True
print(q.enqueue(4))#prints True
print(q.enqueue(5))#prints True
print(q.enqueue(6))#prints True
print(q.enqueue(7))#prints True
print(q.enqueue(8))#prints True
print(q.enqueue(9))#prints Queue Full!
print(q.size())#prints 8
print(q.dequeue())#prints 8
print(q.dequeue())#prints 7
print(q.dequeue())#prints 6
print(q.dequeue())#prints 5
print(q.dequeue())#prints 4
print(q.dequeue())#prints 3
print(q.dequeue())#prints 2
print(q.dequeue())#prints 1
print(q.dequeue())#prints Queue Empty
#Queue is reset here
print(q.enqueue(1))#prints True
print(q.enqueue(2))#prints True
print(q.enqueue(3))#prints True
print(q.enqueue(4))#prints True
Note: Element 9 was not added to the Queue and hence the size of the Queue remains 8
Top comments (0)