Queues in Python

Introduction

Queues are a fundamental data structure in computer science, and it is also covered in the CBSE Class 12 curriculum for Python. Here’s the concepts of what you need to know about:

What is a Queue?

A queue is a linear data structure that follows the First In, First Out (FIFO) principle. Think of it like a line at a store: the first person in line is the first person to be served.

Operations on a Queue:

• Enqueue: Adding an element to the rear (end) of the queue.
• Dequeue: Removing an element from the front (beginning) of the queue.
• Peek: Looking at the element at the front of the queue without removing it.
• isEmpty: Checking if the queue is empty.
• size: Returning the number of elements in the queue.

 

So far, Queues in python are like a “line” or “queue” of customers waiting for service. Customers are serviced in the order in which they arrive on the queue is also called a FIFO list i.e., First In First Out list where the item first inserted is the first to get removed. So, we can say that a queue is a list of data that follows these rules.

1. Data can only be removed from the front end, i.e., the element at the front- end of the queue. The removal of element from a queue is technically called DEQUEUE operation.
2. A new data element can only be added to the rear of the queue. The insertion of element in a stack is technically called ENQUEUE operation.

 

Queues: The Data Structure

In this section “Queues in Python“, we will provide a comprehensive introduction to all useful concepts about queues in python which are used in programing with examples including the following topics

• What are queues in python
• Example of queue’s operations in Python
• How to implment queuess in Python
• Applications of queues in Python

And, by the end of this tutorial, you will have a solid understanding of all about queue data structure in Python like Application of queues, Implementation of queues using python and will be able to use this knowledge in their own python programming projects.

Also this tutorial covers all necessary topics/concepts required to complete your exams preparations in CBSE schools / classes 11th and 12th.

 

 

Queues are similar to stacks in that a queue also consists of a sequence of items (a linear list), and there are restrictions about how items can be added to and removed from the list. However, a queue has two ends, called the front- end and the back- end or rear- end of the queue. Items are always added to the queue at the rear- end and removed from the queue at the front- end. The operations of adding and removing items are called enqueue and dequeue. An item that is added to the back of the queue will remain on the queue until all the items in front of it have been removed.

 

Some Other Queue Terms in Python

There are some other terms related to queues, such as Overflow and Underflow.

Peek:   

Refers to inspecting the value at the queue’s front without removing it; it is also sometimes referred as inspection.

Overflow:

Refers to situation (ERROR) when one tries to enqueue an item in a queue that is full. This situation occurs when the size of the queue is fixed and cannot grow further or there is no memory left to accommodate new item.

Underflow:

Refers to situation (ERROR) when one tries to Dequeue /delete an item from an empty queue. That is, queue is currently having no item and still one tries to dequeue an item.

 

Operations in Queues in python: ENQUEUE and DEQUEUE

Let’s have an example of a bounded Queue of capacity 4 which is initially empty, draw pictures of the queue after each of the following steps.

• Queue empty
• enqueue ‘a’
• enqueue ‘b’
• enqueue ‘c’
• dequeue
• enqueue ‘d’
• enqueue ‘e’
• dequeue
• dequeue
• dequeue
• dequeue

• queue is empty (front= rear= None)

• enqueue ‘a’ (front = 0, rear = 0 )

• enqueue ‘b’ (front = 0, rear = 1)

• enqueue ‘c’ (front = 0, rear = 2)

• dequeue ‘a’ (front = 1, rear = 2)

• enqueue ‘d’ (front = 1, rear = 3)

 

• enqueue ‘e’ (front = 1, rear = 3)

• dequeue ‘b’ (front = 2, rear = 3)

• dequeue ‘c’ (front = 3, rear = 3)

• dequeue ‘d’     (front = None, rear = None)

• dequeue (front = None, rear = None)

Implementing Queues in Python

In python, you can use lists to implement queues. Python offers us a convenient set of methods to operate lists as queues. For various Queue operations, we can use a list say Queue and use python code as described below:     

Peek:                        we can use:       <Queue> [front]                         
                                 where < Queue> is a front is an integer storing the position of first value in the queue 

Enqueue:                  we can use:       <Queue>. append (<item>))

                                 When <item> is the item being pushed in the Queue (i.e., the item will be added at the

                                 rear-end of the queue.

dequeue:                 we can use:         <Queue>.  Pop (0)
                                it removes the first value from the Queue and (i.e., the item at the front-end) and returns it.

 

Program to Implement Queue Operations

“   “     “

queue: implemented as a list
front: integer having position of first (front most) element in queue
rear: integer having position of last element in queue
“   “   “
def cls ( ) :
     print (“\n” * 100)

def is Empty (Qu) :
      if Qu ==[ ] :
          return True
     else :
         return false

def Enqueue (Qu, item) :
     Qu. append (item)
           if len (Qu) == 1 :
              front = rear = 0
          else :
             rear = len (Qu) – 1

def Dequeue (Qu) :
      If is Empty (Qu) :
          return “underflow”
      else :
         item = Qu. pop (0)
         if len (Qu) == 0 :               # if was single-element queue
            front = rear = None
            return item

def peek (Qu) :
     if is Empty (Qu) :
        return “underflow”
    else :
        front = 0
       return Qu [front]

def Display (Qu) :
     if is Empty (Qu) :
        print (“Queue Empty !”)
    elif len (Qu) ==1:
        print (Qu [0], “< ==front, rear”)
   else :
        front = 0
        rear = len (Qu) – 1
        print (Qu[front], “<- front”)
        for a in range (1, rear) :
            print (Qu[a])
       print (Qu[rear], “<-rear”)

#_main_ program
queue = [ ]
front = None
while True:
         cls ( )
             print (“QUEUE OPERATIONS”)
       print (“1. Enqueue”)
       print (“2. Dequeue”)
       print (“3. Peek”)
       print (“4. Display queue”)
       print ( “5. Exit”)
ch = int (input (“Enter your choice (1-5) :” ) )
if ch == 1 :
      item = int (input (“Enter item:” ) )
      Enqueue (queue, item)
      input (“press Enter to continue….”)
elif ch == 2 :
      item = Dequeue (queue)
      if item ==”underflow”
         print (“underflow” : Queue is empty !” )
     else:
         print (“Dequeue-ed  item is”, item
         input (“press Enter to continue….”)
    elif ch == 3:
        item = peek (queue)
        if item ==”underflow”:
        Print (Queue is empty!”)
    else:
        print (“frontmost item is”, item)
       input (“press Enter to continue….”)

elif ch == 4:
     Display (queue)
     input (“press Enter to continue….”)
elif ch == 5:
     break
else:
    print (“Invalid choice!” )
    Input (“press Enter to continue….”)

 

Number of Elements in Queue

We can determine the size of a queue using the formula:
Number of elements n queue = rear- front + 1

In python queues, implemented through lists, the front and rear are:
front = 0 and rear = len (<queue>) – 1

You can also use python function len (<queue>) to get the size of the queue.

Let us now implement a Queue of numbers through a program.

 

Queue Item-nodes

Like stacks, queues can also store information of various types in its item-nodes and if information is logically related then item-node is first create as a list (or any other sequence as per your requirements) and then inserted in the queue. Solved problem 21 implements such a queue.

Variations in Queues in Python

Queues can be used in several forms and ways, depending upon the requirements of the program. Two popular variations of queues are circular Queues and Deque (Double-Ended queues).

 

 Circular Queues in Python

Circular Queues are the queues implemented in circular from rather than a straight line. These are used I programming languages that allow the use of fixed-size linear structures (such as arrays of C/C ++ etc.) as queues. In such queues, after some insertions and deletions, some unutilized space lines in the beginning of the queue. To overcome such problems, circular queues are used that overcome the problem of unutilized spaces in fixed-size linear queues.

Figure shows a circular queue.

Python lists are dynamic structures that can grow and shrink when needed, thus, you don’t need circular queues generally when you are implementing queues through python lists.

Deque (Double-ended Queues) in Python

Deques (double-ended queues) are the refined queues in which elements can be added or removed at either end but not in the middle. There are two variations of a deque- an input restricted deque and an deque output restricted.

• An Input Restricted Deque is a deque which allows insertions at only one end but allows deletions at both ends of the list. [see fig 9.9(a) ]
• An output Restricted Deque is a deque which allows deletions at only one end of the list but allows insertions at both ends of the list. [see fig. 9.9 (b) ]

 

Queues Applications in Python

Queue data structure has found application in many diverse areas. We are discussing here only a few of them, for understanding purposes.

• Any flow of first-in-first-out or first-come-first-served may be implemented as queue. For example, the passengers leave a bus as the order (sequence) they hopped on. (first-in-first-out, last-in-last-out), or a single-lane vehicles into a tunnel, and come out from the other end – all these are real-life applications of queues.
• When a resource is shared among multiple consumers, queues are the best way to implement this type of sharing. For example, in a computer lab, there can be printer being shared among a number of computers. All the computes can send their printing requests to the shared printer. For all the printing requests, printer will maintain a queue and will print on FIFO
• When you make calls to a call center, the call center phone systems will use a queue to hold people in line until a service representative is free.
• Airport authorities make use of queues in situation of sharing a single runway of airport for both landing and take- off of flights.
• When you run multiple programs/ applications on one CPU, and the CPU has to treat each application equally, then CU might use queues to process these applications in phased-manner² (job scheduling)

 

Indirect Applications in Python

• Queues have found indirect usage in many computer applications as auxiliary data structures and components of other data structures.