What is Queue Data Structure In Python?

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:

Need for Queue Data Structure

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.

Daily Life Examples of Queue

Let’s consider some examples where we se queue type working in daily life:

• Phone answering system- Person who calls first on your gadget gets attended first.
• Luggage checking machine– Checks the Luggage that has been kept first on the conveyer belt.
• Vehicles on the toll-tax bridge– The vehicles arriving early leaves first.
• Call Centre– phone systems will use Queues, to hold people calling them in order, until a service representative is free.

All of these examples follow First-In-Last-Out strategy.

Creating a Queue Data Structure

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

• max_size is the maximum number of elements expected in the queue.
• Elements of the queue are stored in the python list
• rear indicates the index position of the last element in the queue.
• The rear is initially taken to be -1 because the queue is empty
• Front indicates the position of the first element in the queue.
• The front is taken to be 0 initially because it will always point to the first element of the queue

Enqueue

Now, when you are trying to enqueue elements to the Queue, you have to remember the following points:

• Whether there is space left in the queue or not i.e. if rear equals max_size -1
• The rear will point to the last element inserted in the queue.

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

De-Queue

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:

• There are elements in the queue i.e. rear should not be equal to -1.
• Secondly, you need to remember that as elements are deleted from the front so, after deleting front should be incremented to point next front.
• The front should not point end of queue i.e. equal to max_size.

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

Dequeued :  None

empty queue

Applications of Queue

As of now, you have already understood the basics of queue. Now to dive deeper we will look into some of its applications.

• Example 1:

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

• Example 2:

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?

1. def fun(n):
2. aqueue = Queue(100)
3. for num in range(1, n+1):
4. enqueue(num)
5. result=1
6. while (not(aqueue.is_empty())):
7. num = aqueue.dequeue()
8. result*=num
9. print(result)

When function fun() is invoked by passing n,

• lines 2 to 4 en-queues the elements from 1 to n
• lines 5 to 8 finds the product of those elements by de-queuing it one by one

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.