Queue Continued...

Queue

Similar to a stack, the queue also limits the position for inserting and removing am operation on a sequence of data. However, unlike a stack, a queue follows the first in, first out (FIFO) principle.

In Python, a queue can also be implemented using a list. To follow the FIFO principle, the inserting operation occurs at the tail of the list, while the removing operation occurs at the head of the list.Python implementation of a queue

Table of Contents

• Queue: Introduction

• Uses of Queues

• Implementing Queues

• Practice Queues

• Conclusion

Queue - An introduction

A Queue is a linear data structure in which data is stored in a First In, First Out manner. In a queue, the item that was added the earliest is removed first. The item that was added more recently is removed last. A queue can be compared to a real-life queue.

Queue, Diagram

enqueue is a queue operation where you add an item at the back of a queue.

dequeue is a queue operation where you remove an item from the front of a queue.

Uses of Queues

• Operating Systems - often maintain queues while implementing various low-level operations such as CPU Scheduling, Disk Scheduling, etc.

• Hardware - hardware interrupts are handled using queues.

• Internet - Website traffic handling.

• And all other scenarios where a First In, First Out priority has to be implemented.

Implementing Queues

Queue Methods

queue.Enqueue()

• The queue.Enqueue() method adds an element at the rear of the queue.

• Time Complexity -> O(1)

queue.Dequeue()

• The queue.Dequeue() method removes an element from the front of the queue.

• Time Complexity -> O(1)

queue.Front()

• The queue.Front() method returns the front item from the queue.

• Time Complexity -> O(1)

queue.Rear()

• The queue.Rear() method returns the rear item from the queue.

• Time Complexity -> O(1)

queue.isEmpty()

• The queue.isEmpty() method returns True if the queue is empty, else returns False.

• Time Complexity -> O(1)

Queues can be implemented in various ways. Let us look at how to implement a queue using a list and using the collections.deque module in Python.

Queue using a List

We can use the list methods insert and pop to implement a queue.

class Queue:

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

    def isEmpty(self) -> bool:
        return True if len(self.queue) == 0 else False

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

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

    def enqueue(self, x: int) -> None:
        self.x = x
        self.queue.insert(0, x)       

    def dequeue(self) -> None:
        self.queue.pop()

Queue using collections.Deque

The deque class from the python collections module can also be used to implement a queue. This method of implementing a queue is far more efficient because deque provides faster enqueue and dequeue operations.

from collections import deque
class Queue:

    def __init__(self):
        """
        Initializing Queue.
        """
        self.queue = deque()

    def isEmpty(self) -> bool:
        return True if len(self.queue) == 0 else False

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

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

    def enqueue(self, x: int) -> None:
        self.x = x
        self.queue.append(x)       

    def dequeue(self) -> None:
        self.queue.popleft()

Practice Queues

Try implementing the queue in Python first. Then once you’re done with the implementation, try solving these problems on HackerRank and LeetCode

• Reversing a Queue - GeeksforGeeks

• Sort the Queue using Recursion - GeeksforGeeks

• Reversing First K Elements of the Queue - GeeksforGeeks

• Implementing Stack using Queues - GeeksforGeeks

• Queries with Fixed Length - HackerRank

• Truck Tour - HackerRank

• Maximum Sum of Triangle No Less Than K - LeetCode

• Design Circular Queue - LeetCode

• Design Circular Dequeue - LeetCode