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

PreviousQueueNextQueue Sandbox

Last updated

Was this helpful?