What Is a FIFO Queue in Python

By /

In Python, a FIFO queue is a linear data structure. It stores objects in a first in first out (FIFO) manner.

For example, you can use the Queue class from the queue module as a thread-safe FIFO queue:

from queue import Queue

namequeue = Queue()

# Add elements
namequeue.put("Alice")
namequeue.put("Bob")
namequeue.put("Charlie")
 
# Remove elements
print(namequeue.get())
print(namequeue.get())
print(namequeue.get())

Output:

Alice
Bob
Charlie

However, you could use a regular list as a FIFO queue as well.

In this guide, you learn how to create a FIFO queue in three ways.

Also, you are going to write some custom classes that implement the FIFO queue.

What Is a Queue

A queue is a linear data structure that stores objects.

A queue works with the FIFO (First In, First Out) principle. Similar to queues in the real world, FIFO means the object who has “waited in the queue” for the longest gets removed first.

Fifo queue

Use Cases for a Queue

There are many ways you can benefit from using a queue.

Generally, whenever your application needs to support the First In, First Out priority, it is time to use a queue.

Here are some common examples:

  1. Internet. The web traffic is handled with a queue that serves clients in the FIFO manner.
  2. Hardware. Hardware interrupts are handled with queues.
  3. Operating Systems. Low-level operations, such as CPU scheduling can be handled with a maintained queue.

Before implementing a queue in Python, let’s go through the necessary operations related to queues.

Queue Operations and Performance

Here are the basic queue operations that a FIFO queue commonly supports:

  1. Enqueue. Add an item to the queue.
  2. Dequeue. Remove an item from the queue. The items are dequeued in the same order as they were enqueued.
  3. Front. Get the first priority item of the queue (on the right).
  4. Rear. Get the last priority item of the queue (on the left).
  5. IsEmpty. Check if the queue is empty.

Now we are ready to get our hands dirty with queues in Python.

Queue Implementations in Python

In this guide, we are going to go through three different ways to create a queue in Python:

  1. list
  2. collections.deque
  3. queue.Queue

Let’s start with a list that can act as a simple FIFO queue.

Python List as a FIFO Queue

A simple way to implement a FIFO queue in Python is by using a list.

A list comes in with useful methods:

  • insert().
  • pop().

These can be used as the enqueue and dequeue methods respectively.

For example, let’s create a queue and add names to it. Then let’s remove the names in the First In, First Out manner:

queue = []

# Add items to queue
queue.append("Alice")
queue.append("Bob")
queue.append("Charlie")

# Remove items from the queue
print(queue.pop(0))
print(queue.pop(0))
print(queue.pop(0))

Output:

Alice
Bob
Charlie

Now you know how to use a list as a FIFO queue in Python.

Next, let’s write a custom class for a queue that implements the operations enqueue, dequeue, front, rear, and isEmpty with the help of a list:

class Queue:
    def __init__(self):
        self.queue = []

    def enqueue(self, x):
        return self.queue.insert(0, x)

    def dequeue(self):
        return self.queue.pop()
    
    def isEmpty(self):
        return len(self.queue) == 0

    def front(self):
        return self.queue[-1]

    def rear(self):
        return self.queue[0]

Now you can use this queue:

namequeue = Queue()

namequeue.enqueue("Alice")
namequeue.enqueue("Bob")
namequeue.enqueue("Charlie")

print("Info about the queue")

front = namequeue.front()
print(f" -The first priority member is {front}")

rear = namequeue.rear()
print(f" -The last priority member is {rear}")

print("Serving the queue:")

next = namequeue.dequeue()
print(f" -served {next}")

next = namequeue.dequeue()
print(f" -served {next}")

next = namequeue.dequeue()
print(f" -served {next}")

Output:

Info about the queue
 -The first priority member is Alice
 -The last priority member is Charlie
Serving the queue:
 -served Alice
 -served Bob
 -served Charlie

Now you know how to use a list as a queue and how to implement a Queue class.

Next, let’s take a look at another approach by using the collections module’s dequeue.

Deque in Python

Deque is a generalization of a queue or a stack.

A deque is a memory-efficient queue.

It comes with O(1) enqueue/dequeue performance, as opposed to the list for which those operations perform at O(n).

Thus, if you need a quicker enqueue/dequeue functionality, do not implement the queue using a list.

Instead, use the collections.dequeue.

For example, let’s add names to a deque and extract them in the priority order:

from collections import deque

queue = deque()

# Add items to queue
queue.appendleft("Alice")
queue.appendleft("Bob")
queue.appendleft("Charlie")

# Remove items from the queue
print(queue.pop())
print(queue.pop())
print(queue.pop())

Output:

Alice
Bob
Charlie

Now you understand how to use a deque as a FIFO queue in Python.

Next, let’s implement a custom Queue class using deque that supports the operations enqueue, dequeue, front, rear, and isEmpty:

from collections import deque

class Queue:
    def __init__(self):
        self.queue = deque()

    def enqueue(self, x):
        return self.queue.appendleft(x)

    def dequeue(self):
        return self.queue.pop()
    
    def isEmpty(self):
        return len(self.queue) == 0

    def front(self):
        return self.queue[-1]

    def rear(self):
        return self.queue[0]

Let’s test the queue:

namequeue = Queue()

namequeue.enqueue("Alice")
namequeue.enqueue("Bob")
namequeue.enqueue("Charlie")

print("Info about the queue")

front = namequeue.front()
print(f" -The first priority member is {front}")

rear = namequeue.rear()
print(f" -The last priority member is {rear}")

print("Serving the queue:")

next = namequeue.dequeue()
print(f" -served {next}")

next = namequeue.dequeue()
print(f" -served {next}")

next = namequeue.dequeue()
print(f" -served {next}")

Output:

Info about the queue
 -The first priority member is Alice
 -The last priority member is Charlie
Serving the queue:
 -served Alice
 -served Bob
 -served Charlie

Let’s make a performance comparison between a deque and a list in Python.

Performance Comparison: Deque vs List

Here is a script that adds to the end of a list and to the end of a deque 100,000 times:

from collections import deque
from time import perf_counter

N = 100_000
items_list = []
items_deque = deque()

def average_time(func, times):
    total = 0.0
    for i in range(times):
        start = perf_counter()
        func(i)
        total += (perf_counter() - start) * 1e3
    return total / times

deque_time = average_time(lambda i: items_deque.appendleft(i), N)
list_time = average_time(lambda i: items_list.insert(0, i), N)
boost = list_time / deque_time

print(f"list.insert():      {list_time:.6} ms")
print(f"deque.appendleft(): {deque_time:.6} ms")
print(f"dequeue is {boost:.4} times faster!")

Output:

list.insert():      0.119216 ms
deque.appendleft(): 0.00381629 ms
dequeue is 31.24 times faster!

As you can see, the deque is significantly faster.

This is because as mentioned earlier, appending to a list is an O(n) operation. But adding to a deque is an O(1) operation.

Last, but not least, let’s take a look at how to use the Queue class from the queue module as a third option to create a FIFO queue in Python.

The Queue Module

If you are running a multi-threaded program and you want to be thread-safe, use the Queue class from the queue module.

This implements a FIFO queue that uses deque behind the scenes.

The Queue class has multiple useful methods:

  • empty().
  • full().
  • get().
  • get_nowait().
  • put().
  • put_nowait().
  • qsize().

Also, you can limit the number of items added to the queue by specifying the maxsize parameter.

Let’s focus on the two thread-safe methods:

  • Queue.put(). This is the enqueue action.
  • Queue.get(). This is the dequeue action.

For example, let’s create a queue of names and empty the queue in the priority order:

from queue import Queue

queue = Queue()

# Add items to queue
queue.put("Alice")
queue.put("Bob")
queue.put("Charlie")

# Remove items from the queue
print(queue.get())
print(queue.get())
print(queue.get())

Output:

Alice
Bob
Charlie

You can also use the Queue class to implement a FIFO queue with the basic operations enqueue, dequeue, rear, front, isEmpty:

Conclusion

Today you learned what is a FIFO queue in Python.

To recap, you can use a list as a FIFO queue in Python. If you need quicker enqueue/dequeue functionality, use deque from the collections module. If you need a quicker and thread-safe FIFO queue, use the Queue class from the queue module.

Thanks for reading.

Happy coding!

Scroll to Top