Data Science and Machine Learning Internship ...
- 22k Enrolled Learners
- Weekend/Weekday
- Live Class
As you have already studied about the importance of Data Structures in the previous article, Lets dive right in the topic of the article i.e. Queue Data Structure. I’ll be discussing the following topics:
Suppose you want for a movie one day. In the multiplex, the tickets were issued on the First-Come-First-Serve basis and people were standing behind each other waiting for their turn. So, what will you do?? You must have gone to the back and stood behind the last person waiting for the ticket.
Here, the people are standing one behind the other and they are serviced based on the First-In-First-Out (FIFO) mechanism. Such an arrangement is known as a Queue.
Let’s consider some examples where we se queue type working in daily life:
All of these examples follow First-In-Last-Out strategy.
Apart from the complementary operations, I may say that the main Operations possible on the Queue are:
1. En-queue or add an element to the end of the queue.
2. De-queue or remove an element from the front of the queue
Now, let’s start via creating class Queue in Python:
class Queue: def __init__(self,max_size): self.__max_size=max_size self.__elements=[None]*self.__max_size self.__rear=-1 self.__front=0
Now, when you are trying to enqueue elements to the Queue, you have to remember the following points:
So, what will be the algorithm??
#returns max_size of queue def get_max_size(self): return self.__max_size #returns bool value whether queue is full or not, True if full and False otherwise def is_full(self): return self.__rear==self.__max_size-1 #inserts/enqueue data to the queue if it is not full def enqueue(self,data): if(self.is_full()): print("Queue is full. No enqueue possible") else: self.__rear+=1 self.__elements[self.__rear]=data #display all the content of the queue def display(self): for i in range(0,self.__rear+1): print(self.__elements[i]) #You can use the below __str__() to print the elements of the DS object while debugging def __str__(self): msg=[] index=self.__front while(index<=self.__rear): msg.append((str)(self.__elements[index])) index+=1 msg=" ".join(msg) msg="Queue data(Front to Rear): "+msg return msg
Now, When you execute the following:
queue1=Queue(5)
#Enqueue all the required element(s).
queue1.enqueue(“A”)
queue1.enqueue(“B”)
queue1.enqueue(“C”)
queue1.enqueue(“D”)
queue1.enqueue(“E”)
queue1.display()
queue1.enqueue(“F”)
print(queue1)
Output:
A
B
C
D
E
Queue is full. No enqueue possible
Queue data(Front to Rear): A B C D E
Now, as you have inserted/enqueued the elements into the queue, you want to dequeue/delete them from front, so you need to take care of following:
So, what will be the algorithm??
#function to check if queue is empty or not def is_empty(self): if(self.__rear==-1 or self.__front==self.__max_size): return True else: return False #function to deque an element and return it def dequeue(self): if(self.is_empty()): print("queue is already empty") else: data=self.__elements[self.__front] self.__front+=1 return data #function to display elements from front to rear if queue is not empty def display(self): if(not self.is_empty()): for i in range(self.__front,self.__rear+1): print(self.__elements[i]) else: print("empty queue")
Now when you execute the following :
queue1=Queue(5)
#Enqueue all the required element(s)
queue1.enqueue(“A”)
queue1.enqueue(“B”)
queue1.enqueue(“C”)
queue1.enqueue(“D”)
queue1.enqueue(“E”)
print(queue1)
#Dequeue all the required element(s)
print(“Dequeued : “, queue1.dequeue())
print(“Dequeued : “, queue1.dequeue())
print(“Dequeued : “, queue1.dequeue())
print(“Dequeued : “, queue1.dequeue())
print(“Dequeued : “, queue1.dequeue())
print(“Dequeued : “, queue1.dequeue())
#Display all the elements in the queue.
queue1.display()
Output:
Queue data(Front to Rear): A B C D E
Dequeued : A
Dequeued : B
Dequeued : C
Dequeued : D
Dequeued : E
queue is already empty
empty queue
As of now, you have already understood the basics of queue. Now to dive deeper we will look into some of its applications.
Print Queue in Windows uses a queue to store all the active and pending print jobs. When we want to print documents, we issue print commands one after the other. Based on the print commands, the documents will get lined up in the print queue. When the printer is ready, the document will be sent in first in first out order to get it printed.
Suppose you have issued print commands for 3 documents in the order doc1, followed by doc2 and doc3.
The print queue will be populated as shown below:
doc-n, where the doc is the document sent for printing and n, is the number of pages in the document. For example, doc2-10 means doc2 is to be printed and it has 10 pages. Here is a code that simulates print queue operation. Go through the code and observe how the queue is used in this implementation.
class Queue: def __init__(self,max_size): self.__max_size=max_size self.__elements=[None]*self.__max_size self.__rear=-1 self.__front=0 def is_full(self): if(self.__rear==self.__max_size-1): return True return False def is_empty(self): if(self.__front>self.__rear): return True return False def enqueue(self,data): if(self.is_full()): print("Queue is full!!!") else: self.__rear+=1 self.__elements[self.__rear]=data def dequeue(self): if(self.is_empty()): print("Queue is empty!!!") else: data=self.__elements[self.__front] self.__front+=1 return data def display(self): for index in range(self.__front, self.__rear+1): print(self.__elements[index]) def get_max_size(self): return self.__max_size #You can use the below __str__() to print the elements of the DS object while #debugging def __str__(self): msg=[] index=self.__front while(index<=self.__rear): msg.append((str)(self.__elements[index])) index+=1 msg=" ".join(msg) msg="Queue data(Front to Rear): "+msg return msg #function that enqueue are the documents to be printed in Queue named print_queue def send_for_print(doc): global print_queue if(print_queue.is_full()): print("Queue is full") else: print_queue.enqueue(doc) print(doc,"sent for printing") #function that prints the document if number of pages of document is less than #total number of pages in printer def start_printing(): global print_queue while(not print_queue.is_empty()): #here we dequeue the Queue and take the coument that was input first for printing. doc=print_queue.dequeue() global pages_in_printer #the aim of this for loop is to find number of pages of the of document which is doc name followed by “-“ for i in range(0,len(doc)): if(doc[i]=="-"): no_of_pages=int(doc[i+1:]) break if(no_of_pages<=pages_in_printer): print(doc,"printed") pages_in_printer-=no_of_pages print("Remaining no. of pages in printer:", pages_in_printer) else: print("Couldn't print",doc[:i],". Not enough pages in the printer.") pages_in_printer=12 print_queue=Queue(10) send_for_print("doc1-5") send_for_print("doc2-3") send_for_print("doc3-6") start_printing()
Output:
doc1-5 sent for printing
doc2-3 sent for printing
doc3-6 sent for printing
doc1-5 printed
Remaining no. of pages in printer: 7
doc2-3 printed
Remaining no. of pages in printer: 4
Couldn’t print doc3 . Not enough pages in the printer
Let’s try to understand another example which uses Queue data structure. Can you try to understand the code and tell what the following function does?
When function fun() is invoked by passing n,
With this, we come to an end of this Queue Data Structure article. If you successfully understood and ran the codes by yourselves you are no longer a newbie to Queue Data Structure.
Got a question for us? Please mention it in the comments section of this article and we will get back to you as soon as possible.
To get in-depth knowledge on Python along with its various applications, you can enroll for live Python online training with 24/7 support and lifetime access.
Course Name | Date | Details |
---|---|---|
Python Programming Certification Course | Class Starts on 28th September,2024 28th September SAT&SUN (Weekend Batch) | View Details |
edureka.co