Queue Data Structure and Implementation in Python

Overview

Queue is a linear data structure through which we follow elements are accessed from the both ends and it follows the FIFO (first in first out) principle.

Let us understand the first in first out principle (FIFO) with the help of an example, suppose we are standing in a assembly line in the school the student who first enters in the assembly queue goes out from the queue first.

The side at which the elements are inserted are known as the rear while the side at which the elements are deleted are known as the front.

Scope of the article

• In this article we will learn read about the different operation we can perform in the queue.
• We will also read about the different types of queue with its implementation in python.
• We will also read about the applications of queue.

Introduction

Now since we already know that the queue follows the first in first out (FIFO) principle and is widely used by us in our daily life.

Now let us read about the different operation we can perform in a queue:

1. Enqueue
2. Dequeue
3. Isempty
4. Isfull
5. Peek
6. Front
7. Rear

Now let us read about each of these operations in details:

Enqueue:

This operation is used to add elements in the queue. If in any condition the rear index excedes the size of the queue then we can say that the queue is full and then it is said to be in an overflow condition.

The time complexity to perform this operation is O(1).

Dequeue:

Since the enqueue operation is used to insert elements in the queue so the dequeue operation is used to delete the elements from the queue. If the rear points to -1 that is there are no more elements to delete then we can say that the queue is in the underflow condition.

The time complexity to perform this operation is O(1).

Isempty:

This operation in the queue is used to check whether the queue is empty or not.

Isfull:

By the word isfull we can understand that this operation is used to check whether the queue is full or not.

Peek:

This operation is used to find the peek element that is the first element of the queue without deleting. It returns the value of the first element without deleting it.

Front:

This operation is used to get the first element from the queue. The time complexity to perform this operation is O(1).

Rear:

This operation is used to get the last element from the queue. The time complexity to perform the rear operation in queue is O(1).

Now since we have read about the operation which we can perform in the queue let us see the implementation of queue in python:

Implementation of queue in python:

queue1 = []
queue1.append('1')
queue1.append('4')
queue1.append('9')
queue1.append('87')
queue1.append('75')
print("Currently present elements present in the queue are :")
print(queue1)
print("The elements which are dequeued from the queue are ")
print(queue1.pop(0))
print(queue1.pop(0))
print(queue1.pop(0))
print(queue1.pop(0))
print("\nThe present elements present in the queue after removing the elements are :")
print(queue1)

Output

Initial elements which are present in the queue are
['1', '4', '9', '87', '75']

Elements which are dequeued from the queue  are
1
4
9
87

The present elements presnent in the queue after removing the elements are :
['75']

In the above code firstly we have added five elements in the queue then using the pop operation we have deleted the first four elements which were present in the queue.

Run the above code in your editor for a better and clear explanation.

Now lets us see the queue implementation using list in python:

queue=[]
def Enqueue():
    if len(queue)==size: 
        print("overflow!!Cannot insert more elements")
    else:
        element=input("Enter the element which u want to insert:")
        queue.append(element)
        queue.append(element)
        print("the above elements are added to the queue")
def dequeue():
    if not queue:
        print("Cannot delete more elements from the queue , Underflow condition!!!")
    else:
        removed_element=queue.pop(0)
        removed_element=queue.pop(0)
        print("The removed element from the queue are!!:",removed_element)
def display():
    print(queue)
    size=int(input("Enter the size of Queue which u want :"))
    while True:
        print("Select the Operation of your choices:1.Add elements in the queue 2.Delete elements from the queue 3. Display the current elenents from the queue 4. Exit from the queue ")
        choice=int(input())
        if choice==1:
            Enqueue()
        elif choice==2:
            dequeue()
        elif choice==3:
            display()
        elif choice==4:
            break
        else:
            print("Invalid Option! enter any other option")

In the above code using list in python we have implemented three operations that is enqueue, dequeue, display in a queue. We have created seperate functions for each of them.

Run the code in your editor for a better and clear explanation.

Now lets us read about the types of queue:

Types of queues:

They are mainly four type of queues in python. They are as follows:

1. Simple Queue
2. Circular Queue
3. Priority Queue
4. Double Ended Queue

Now let us read about each of them in details:

1. Simple queue

The simple queue is the normal queue in which the insertion and deletion of elements follow the FIFO(first in first out) principle.

There are mainly disadvantages of using the simple queue that is it the elements which enter first , are removed first hence suppose we have a queue of 10 elements if we delete all the 8 elements and only 2 are left then also we cannot add elements .

2. Circular Queue:

In this queue the last node is connected to the first element of the queue , this queue solves the problem of the simple queue that is if we want to add elements in the starting and empty space is present then we can directly add elements to the queue.

3. Priority Queue

In this the elements of the queue are arranged according to priority. The elements with high priority are arranged according to the FIFO (first in first out) principle.

4. Deque

In this type of queue we get a benefit that we can insert as well as delete elements from both sides of the queue either from the rear or front ends. A good example of a string is a no whose reverse is similar to its original.

Application of queue in python:

Queue is used by in real word too like suppose we are standing in a assembly line in the school the student who first enters in the assembly queue goes out from the queue first. Queues are also used in cd players.

And is also used in the famous social media platform, Whatsapp. Queues are also mainly used in scheduling algorithms. These are few applications of queue which is used by us in our daily life.

Conclusion

1. Queue follows the first in first out principle and is very useful in our day to day life,
2. Queues are used to implement various Cpu scheduling algorithms.
3. In this article we have studied abou the different operations of queue with examples.
4. We have also read about the types of queue with their uses in this article.