# Queue in Python

## Introduction

Queue in Python Programming is one of the linear data structures used to store data in memory. The queue is a linear data structure that stores data sequentially based on the **First In First Out** (**FIFO**) manner and is also known as the **First Come First Served** data structure. A queue has two ends, namely- **rear** and **front**. The data or an element is inserted from the rear end, on the other hand, elements are removed from the front end.

## 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.

**Note:**

A linear data structure is a collection of elements such that each element is arranged sequentially, and each member element is connected to its previous and next elements.

In our day-to-day life, we can see many examples of queues. The queue for a movie ticket is an example of a queue data structure. The person standing in front of the ticket window will get the ticket first.

The queue in python can be implemented in a variety of ways. The queue in python has two ends, namely- **rear** and **front**. The data or an element is inserted from the rear end. On the other hand, elements are removed from the front end.

A pictorial representation of a queue can be:

## 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)$**.

**Note:**

If a queue is full, then we cannot insert any new element into the queue. This condition is known as **overflow condition**.

:::section.{main}

**2. Dequeue**

Deleting or removing an element of data from the queue is known as **dequeue**. An element is deleted or dequeued from the front end of the queue.
Since the front end is always maintained, we can directly delete an element from the queue. So, the time complexity of deleting an element from the queue in python is **$O(1)$**.

:::

**Note:**

If a queue is empty, then we cannot remove any element from the queue. This condition is known as the **underflow condition**.

**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)$**.

**Note:**

As we can see, nearly all of the operations associated with the queue in python take a linear time, i.e., **$O(1)$**. Hence, the queue is a fast and effective data structure.

## 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.

**Note:**

If we are implementing a queue using a list, then the append() method is used in place of the enqueue() method, and the pop() method is used in place of the dequeue() method.

Let’s see the implementation code:

**Output:**

### Implementation using collections.deque

In python, we have a class called **dequeue class** under the **collection** module. We can also implement the queue in python using the collection modules’ dequeue class.

One of the advantages of using the collection module is that appending and deleting elements takes a constant amount of time i.e., **O(1)** time complexity only.

**Note:**

If we are implementing a queue using the dequeue class of the collection module, then the append() method is used in place of the enqueue() method, and the popleft() method is used in place of the dequeue() method.

Let’s see the implementation code:

**Output:**

### Implementation using queue.Queue

In python, we have a module called **Queue**. We can also implement the queue in python using the Queue module.

One of the advantages of using the Queue module is that we can initialize an infinite-sized queue. To initialize an infinite queue, we can set the maxsize variable to 0. For example: Queue(maxsize = 0).

**Note:**

The Queue collection provides us with various methods and variables. One of the most important variables is maxsize. The maxsize variable sets the queue size (or the number of items allowed inside the queue).

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.

## Conclusion

- 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.
- Queue is a linear data structure that stores data sequentially based on the
**First In First Out**(**FIFO**) manner. The queue data structure is also known as the**First Come, First Serve**data structure. - The queue in python has two ends, namely-
**rear**and**front**. The data or an element is inserted from the rear end. On the other hand, elements are removed from the front end. - Queue in python can be implemented using a list data structure, the dequeue class of the Collection module, Queue module, and by defining our class.
- Some of the most commonly used queue methods are: enqueue(element), dequeue(), empty(), full(), front(), and rear().