Queue in Python

Introduction to Queue in Python

A data structure is a way of organizing data for easy, faster, and effective usage.

Queue in python is one of the linear data structures used to store data in the memory. We can define a queue as a linear data structure that stores data sequentially based on the First In First Out (FIFO) manner. So, the data inserted first will be removed from the queue first. Since the first element inserted is served and removed, the queue data structure is also known as the First Come First Served data structure.

Operations of Queue in Python

Queue in python is one of the most important and commonly used data structures. We can perform various operations using queues in python. Let us learn about the various operation associated with queues in python.

1. Enqueue

Inserting an element of data into the queue is known as enqueue. An element is inserted or enqueued from the rear end of the queue.

Since the rear end is always maintained, we can directly insert a new element into the queue. So, the time complexity of inserting an element in the queue in python is $O(1)$.

3. Front

The front is a pointer that points to the element first inserted into the queue. The front of a queue helps us to get the oldest element present in the queue. So, the time complexity of getting the front element of the queue in python is $O(1)$.

4. Rear

The rear is a kind of pointer that points to the element which is last inserted into the queue. The rear of a queue helps us to get the newest element present in the queue. So, the time complexity of getting the rear element of the queue in python is $O(1)$.

Methods Available in Queue

The queue is one of the fastest (insertion and deletion can be performed in O(1) time complexity) and most frequently used data structures. So, the queue in python supports a wide range of methods. Let us now discuss some of the commonly used methods associated with the queue in python.

1. put(item)

The queue provides the put(item) method in python to insert an element into the queue. The put(item) method uses the rear pointer to insert an element in the queue.

2. get()

The queue provides the get() method in python to get or extract an element from the queue. The get() method uses the front pointer to get an element of the queue.

3. empty()

The empty() method is provided by the queue in python to check whether the queue is empty. The empty() method uses the front pointer and returns a boolean value. The queue is empty if the empty() method returns true. Else, the queue has some elements in it.

4. qsize()

The qsize() method is provided by the queue in python to get the size, i.e., the number of elements present in the queue.

5. full()

The full() method is vice versa of the empty() method. The full() method is provided by the queue in python to check whether the queue is full or not. The full() method uses the rear pointer and returns a boolean value. If the full() method returns true, the queue is filled with no space left.

Implementation of Queue in Python

As we have discussed, we can implement the queue in python in several ways. Let us discuss the various ways one by one.

Implementation using list

We can implement a queue in python using a list. The list is a built-in linear data structure present in python. For inserting and deleting an element from the list queue, we need to shift the entire elements present in the queue(list). Hence, the list implementation is slower as the inserting and deleting elements take O(N) time.

Let’s see the implementation code:

Output:

Using a user-defined linked list

So far, we have discussed the built-in methods, classes, and modules to implement a queue in python. Let us now create our queue class and implement the queue methods.

The implementation code:

Output:

Examples of Queue in Python

Let us now takes a few examples and implement different methods and algorithms on the queue. We will take the list-based implementation of the queue in python.

Example 1: Sorting the Queue

Let us try to sort the elements of a queue. Since the queue is implemented using the list, we can use the built-in sort() method. Let's see the implementation:

Output:

Adding Element to a Queue

To add an element (enqueue), we can use the built-in list method 'append()`. Let's see the implementation:

Output:

Example 2: Removing Element from a Queue

To remove an element (dequeue), we can simply use the built-in list method 'pop()`. Let's see the implementation:

Output:

Application of Queue in Python

Let us now discuss various applications of the queue:

• Queue data structure is used to implement FCFS CPU scheduling algorithm, i.e., first come, first serve scheduling.
• Queue is also used for spooling in printers and as a buffer for various input devices.
• Queue is used in disk scheduling by the Operating Systems.
• Queue is used in handling website traffic.
• Queue is also used in maintaining the playlist in media players.
• Queue is also used to maintain the processes in the waiting queue for the CPU processing.

There are various other uses of the queue. Many tree and graph algorithms use queue data structures like level order traversal, etc.

See Also:

• insert() in Python
• linked list in Python
• pop() in python