Python Queue: FIFO, LIFO Example

Details

What is Python Queue?

A queue is a container that holds data. The data that is entered first will be removed first, and hence a queue is also called "First in First Out" (FIFO). The queue has two ends front and rear. The items are entered from the rear and removed from the front side.

In this Python tutorial, you will learn:

How does Python Queue Work?

The queue can be easily compared with the real-world example the line of people waiting in a queue at the ticket counter, the person standing first will get the ticket first, followed by the next person and so on. The same logic goes for the queue data structure too.

Here is a diagrammatic representation of queue:

The Rear represents the point where the items are inserted inside the queue. In this example, 7 is value for that.

The Front represents the point where the items from the queue will be removed. If you remove an item from the queue, the first element you will get is 1, as shown in the figure.

Item 1 was the first one to be inserted in the queue, and while removing it is the first one to come out. Hence the queue is called FIRST IN FIRST OUT (FIFO)

In a queue, the items are removed in order and cannot be removed from in between. You just cannot remove the item 5 randomly from the queue, to do that you will have to remove all the items before 5. The items in queue will be removed in the order they are inserted.

Types of Queue in Python

There are mainly two types of queue in Python:

  • First in First out Queue: For this, the element that goes first will be the first to come out.

    To work with FIFO, you have to call Queue() class from queue module.

  • Last in First out Queue: Over here, the element that is entered last will be the first to come out.

    To work with LIFO, you have to call LifoQueue() class from the queue module.

Python queue Installation

It is very easy to work with queue in python. Here are the steps to follow to make use of queue in your code.

Step 1) You just have to import the queue module, as shown below: 

import queue

The module is available by default with python, and you don't need any additional installation to start working with the queue. There are 2 types of queue FIFO (first in first out) and LIFO (last in first out).

Step 2) To work with FIFO queue , call the Queue class using the queue module imported as shown below: 

import queue
q1 = queue.Queue()

Step 3) To work with LIFO queue call the LifoQueue() class as shown below: 

import queue
q1 = queue.LifoQueue()

Methods available inside Queue and LifoQueue class

Following are the important methods available inside Queue and LifoQueue class:

  • put(item): This will put the item inside the queue.
  • get(): This will return you an item from the queue.
  • empty(): It will return true if the queue is empty and false if items are present.
  • qsize(): returns the size of the queue.
  • full(): returns true if the queue is full, otherwise false.

First In First Out Queue Example

In the case of first in first out, the element that goes first will be the first to come out.

Add and item in a queue

Let us work on an example to add an item in a queue. To start working with the queue, first import the module queue, as shown in the example below.

To add an item , you can make use of put() method as shown in the example: 

import queue
q1 = queue.Queue()
q1.put(10) #this will additem 10 to the queue.

By default, the size of the queue is infinite and you can add any number of items to it. In case you want to define the size of the queue the same can be done as follows 

import queue
q1 = queue.Queue(5) #The max size is 5.
q1.put(1)
q1.put(2)
q1.put(3)
q1.put(4)
q1.put(5)
print(q1.full()) # will return true.

Output: 

True

Now the size of the queue is 5, and it will not take more than 5 items, and the method q1.full() will return true. Adding any more items will not execute the code any further.

Remove an item from the queue

To remove an item from the queue, you can use the method called get(). This method allows items from the queue when called.

The following example shows how to remove an item from the queue. 

import queue
q1 = queue.Queue()
q1.put(10)

item1 = q1.get()

print('The item removed from the queue is ', item1)

Output: 

The item removed from the queue is  10

Last In First Out queue Example

In the case of last in the first out queue, the element that is entered last will be the first to come out.

To work with LIFO, i.e., last in the first out queue, we need to import the queue module and make use of the LifoQueue() method.

Add and item in a queue

Here we will understand how to add an item to the LIFO queue. 

import queue
q1 = queue.LifoQueue()
q1.put(10)

You have to use the put() method on LifoQueue, as shown in the above example.

Remove an item from the queue

To remove an item from the LIFOqueue you can make use of get() method . 

import queue
q1 = queue.LifoQueue()
q1.put(10)

item1 = q1.get()

print('The item removed from the LIFO queue is ', item1)

Output:

The item removed from the LIFO queue is  10

Add more than 1 item in a Queue

In the above examples, we have seen how to add a single item and remove the item for FIFO and LIFOqueue. Now we will see how to add more than one item and also remove it.

Add and item in a FIFOqueue

import queue
q1 = queue.Queue()

for i in range(20):
    q1.put(i) # this will additem from 0 to 20 to the queue

Remove an item from the FIFOqueue

import queue
q1 = queue.Queue()

for i in range(20):
    q1.put(i) # this will additem from 0 to 20 to the queue

while not q1.empty():
print("The value is ", q1.get()) # get() will remove the item from the queue.

Output: 

The value is  0
The value is  1
The value is  2
The value is  3
The value is  4
The value is  5
The value is  6
The value is  7
The value is  8
The value is  9
The value is  10
The value is  11
The value is  12
The value is  13
The value is  14
The value is  15
The value is  16
The value is  17
The value is  18
The value is  19

Add and item in a LIFOqueue

import queue
q1 = queue.LifoQueue()
for i in range(20):
    q1.put(i) # this will additem from 0 to 20 to the queue

Remove an item from the LIFOqueue

import queue
q1 = queue.LifoQueue()

for i in range(20):
    q1.put(i) # this will additem from 0 to 20 to the queue


while not q1.empty():
print("The value is ", q1.get()) # get() will remove the item from the queue.

Output: 

The value is  19
The value is  18
The value is  17
The value is  16
The value is  15
The value is  14
The value is  13
The value is  12
The value is  11
The value is  10
The value is  9
The value is  8
The value is  7
The value is  6
The value is  5
The value is  4
The value is  3
The value is  2
The value is  1
The value is  0

Sorting Queue

Following example shows the queue sorting.The algorithm used for sorting is bubble sort. 

import queue
q1 = queue.Queue()
#Addingitems to the queue
q1.put(11)
q1.put(5)
q1.put(4)
q1.put(21)
q1.put(3)
q1.put(10)

#using bubble sort on the queue
n =  q1.qsize()
for i in range(n):
    x = q1.get() # the element is removed
    for j in range(n-1):
        y = q1.get() # the element is removed
        if x > y :  
            q1.put(y)   #the smaller one is put at the start of the queue
        else:
            q1.put(x)  # the smaller one is put at the start of the queue
            x = y     # the greater one is replaced with x and compared again with nextelement
    q1.put(x)

while (q1.empty() == False): 
print(q1.queue[0], end = " ")  
        q1.get()

Output: 

3 4 5 10 11 21

Reversing Queue

To reverse the queue, you can make use of another queue and recursion.

The following example shows how to get the queue reversed.

Example: 

import queue
q1 = queue.Queue()

q1.put(11)
q1.put(5)
q1.put(4)
q1.put(21)
q1.put(3)
q1.put(10)

def reverseQueue (q1src, q2dest) :  
    buffer = q1src.get()
    if (q1src.empty() == False) :
reverseQueue(q1src, q2dest)      #using recursion
    q2dest.put(buffer)
return q2dest

q2dest = queue.Queue()
qReversed = reverseQueue(q1,q2dest)

while (qReversed.empty() == False): 
print(qReversed.queue[0], end = " ")  
        qReversed.get()

Output: 

10 3 21 4 5 11

Summary:

  • A queue is a container that holds data. There are two types of Queue, FIFO, and LIFO.
  • For a FIFO (First in First out Queue), the element that goes first will be the first to come out.
  • For a LIFO (Last in First out Queue), the element that is entered last will be the first to come out.
  • An item in a queue is added using the put(item) method.
  • To remove an item, get() method is used.