DSA: Introduction to Queues

Queues are a fundamental concept in computer science and are widely used in data structures and algorithms. Let’s break down the concept of queues and see how you can work with them in Python.

What is a Queue?

A queue is a linear data structure that follows the First-In-First-Out (FIFO) principle. This means that the first element added to the queue will be the first one to be removed. Think of it like a line at a ticket counter: the person who gets in line first is the first to be served.

Key Operations in Queues

Queues support several basic operations:

1. Enqueue: Adding an element to the end of the queue.
2. Dequeue: Removing an element from the front of the queue.
3. Front/Peek: Getting the element at the front of the queue without removing it.
4. IsEmpty: Checking if the queue is empty.
5. Size: Getting the number of elements in the queue.

Creating a Queue in Python

Python does not have a built-in queue data structure, but you can use a list to create a simple queue. However, using a list for queues is not efficient for large data sets because removing elements from the front of the list is slow. Instead, you can use the collections.deque module, which provides a double-ended queue and is optimized for appending and popping elements from both ends.

Implementing of Queues using a List

• The queue is a collection of elements that follows the First In, First Out (FIFO) principle. This means the first element added to the queue will be the first one to be removed.

• Instead of enqueue() and dequeue(), the append() and pop() functions are utilized. However, lists are quite slow for this purpose since inserting or deleting a member at the beginning requires shifting all other elements by one, which takes O(n) time.

• The code makes use of a Python list to imitate a queue. It adds items ‘u’, ‘v’, and ‘w’ to the queue, then dequeues them, leaving an empty queue at the end. The output displays the original queue, the elements dequeued (‘u’, ‘v’, and ‘w’), and the queue’s empty state.

For example in Python:

Input:

queue = []
queue.append('u')
queue.append('v')
queue.append('w')
print("Initial queue")
print(queue)
print("\nElements dequeued from queue")
print(queue.pop(0))
#prints the first popped out element

print(queue.pop(0))
#prints the second popped out element

print(queue.pop(0))
#prints the third popped out element

print("\nQueue after removing elements")
print(queue)

Output:

Initial queue
['a', 'b', 'c']
Elements dequeued from queue
a
b
c
Queue after removing elements
[]

If you pop an empty list:

Traceback (most recent call last):
  File "/desktop/python/zf51fch087998dsd70d456w45g19b6de.py", line 30, in 
    print(queue.pop(0))
IndexError: pop from empty list

Implementation using collections.deque

Here’s how you can create and use a queue with ‘deque’ in Python:

from collections import deque

# Create a queue
queue = deque()

# Enqueue elements
queue.append('a')
queue.append('b')
queue.append('c')

# Dequeue an element
print(queue.popleft())  # Output: 'a'

# Check the front element
print(queue[0])  # Output: 'b'

# Check if the queue is empty
print(len(queue) == 0)  # Output: False

# Get the size of the queue
print(len(queue))  # Output: 2

Implementation using queue.Queue

The queue module in Python is a built-in module used to implement a queue. When you initialize a variable with queue.Queue(maxsize), it sets the queue’s maximum size to maxsize. If you set maxsize to zero (0), the queue becomes infinite. This queue follows the First-In-First-Out (FIFO) rule. Here are some functions available in this module:

• put(item): Adds an item to the queue.
• get(): Removes and returns an item from the queue.
• task_done(): Signals that a task is complete.
• join(): Blocks until all items in the queue have been processed.
• qsize(): Returns the number of items in the queue.
• empty(): Checks if the queue is empty.
• full(): Checks if the queue is full.
• put_nowait(item): Adds an item to the queue without waiting. Raises queue.Full if the queue is full.
• get_nowait(): Removes and returns an item from the queue without waiting. Raises queue. Empty if the queue is empty.

For Example in Python: 

This code utilizes the Queue class from the queue module. It starts with an empty queue and fills it with ‘u’, ‘v’, and ‘w’. After dequeuing, the queue becomes empty, and ‘1’ is added. Despite being empty earlier, it remains full, as the maximum size is set to 3. The code demonstrates queue operations, including checking for fullness and emptiness.

from queue import Queue
q = Queue(maxsize = 4)
print(q.qsize())
q.put('u')
q.put('v')
q.put('w')
print("\nFull: ", q.full()) 
print("\nElements dequeued from the queue")
print(q.get())
#prints the first dequeued element

print(q.get())
#prints the second dequeued element

print(q.get())
#prints the third dequeued element

print("\nEmpty: ", q.empty())
q.put(1)
print("\nEmpty: ", q.empty()) 
print("Full: ", q.full())

Output:

0
Full:  True
Elements dequeued from the queue
u
v
w
Empty:  True
Empty:  False
Full:  False

Implementing a Queue Class

To understand queues better, you can implement your own queue class. Here’s a simple implementation in Python:

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

    def enqueue(self, item):
        self.queue.append(item)

    def dequeue(self):
        if not self.is_empty():
            return self.queue.popleft()
        return None

    def front(self):
        if not self.is_empty():
            return self.queue[0]
        return None

    def is_empty(self):
        return len(self.queue) == 0

    def size(self):
        return len(self.queue)

# Using the Queue class
q = Queue()
q.enqueue(1)
q.enqueue(2)
q.enqueue(3)

print(q.dequeue())  # Output: 1
print(q.front())    # Output: 2
print(q.is_empty()) # Output: False
print(q.size())     # Output: 2

In this implementation:

• The ‘enqueue’ method adds an item to the end of the queue.
• The ‘dequeue’ method removes and returns the front item to the queue.
• The ‘front’ method returns the front item without removing it.
• The ‘is_empty’ method checks if the queue is empty.
• The ‘size’ method returns the number of items in the queue.

Real-World Applications of Queues

Queues are used in various real-world applications:

• Task Scheduling: Operating systems use queues to manage tasks.

• Customer Service: Help desks use queues to manage customer requests.

• Breadth-First Search (BFS): This algorithm uses queues to explore nodes level by level in a graph or tree.