Concept#

Twitter Handle LinkedIn Profile Tag Tag Tag

The Queue Abstract Data Type#

The idea is first-in-first-out.

Consider a queue at a restaurant, it starts off as empty, so we denote an empty queue as an empty list q = [].

  • First, person 1 p1 came to queue, we place him into the queue q and call this enqueue and say that q.enqueue(p1) -> q = [p1];

  • Then, person 2 p2 came to queue, we place him into the queue q using enqueue and say that q.enqueue(p2) -> q = [p2, p1], note carefully we are inserting at the start of the list, as we are treating the end of a list as the start of the queue, and therefore p2 has to be slotted after p1, which is an insertion;

  • If we want to serve the queue, the first one in the queue will get called, we call this dequeue and say that q.dequeue(), which returns p1 and at the same time remove p1 from the queue, so now q = [p2]. Note dequeue does not take in argument.

Implementing Queue Using List#

Python Implementation#

from __future__ import annotations

from typing import Generic, TypeVar, List

T = TypeVar("T")


class QueueList(Generic[T]):
    """Creates a queue that uses python's default list as the underlying
    data structure.

    Attributes:
        queue_items (List[T]): The list that stores the items in the queue.
            We treat the end of the list as the start of the queue and
            the start of the list as the end of the queue.
    """

    _queue_items: List[T]

    def __init__(self) -> None:
        self._queue_items = []

    def __len__(self) -> int:
        """Return the size of the queue."""
        return len(self.queue_items)

    def __iter__(self) -> QueueList[T]:
        """Iterate over the queue items."""
        return self

    def __next__(self) -> T:
        """Return the next item in the queue."""
        if self.is_empty():
            raise StopIteration
        return self.dequeue()

    @property
    def queue_items(self) -> List[T]:
        """Read only property for the queue items."""
        return self._queue_items

    @property
    def size(self) -> int:
        """Return the size of the queue.

        Returns:
            (int): The size of the queue.
        """
        return len(self)

    def is_empty(self) -> bool:
        """Check if queue is empty.

        Returns:
            (bool): True if queue is empty, False otherwise.
        """
        return self.size == 0

    def enqueue(self, item: T) -> None:
        """Insert an item at the end of the queue.

        In this implementation, the item is inserted at the start of the list.

        Args:
            item (T): The current item to be queued.
        """
        self.queue_items.insert(0, item)

    def dequeue(self) -> T:
        """Pop an item from the start of the queue.

        In this implementation, the item at the end of the list is returned and removed.
        We are using the list's pop method to do this.

        Raises:
            (Exception): If queue is empty.

        Returns:
            (T): The item at the start of the queue.
        """
        if self.is_empty():
            raise Exception("Queue is empty")
        return self.queue_items.pop()

We push 4 items in this sequence 4, dog, True, 8.4 and now the “top” of the stack is 8.4.

So as we pop them, it goes from 8.4, True, dog, 4.

q = QueueList()

q.enqueue(4)
q.enqueue("dog")
q.enqueue(True)
print(q.size)

q.enqueue(8.4)
print(q.dequeue())
print(q.dequeue())
print(q.size)
3
4
dog
2

Time Complexity#

Table 62 Time Complexity of Queue Implemented using List#

Operations

Time Complexity

enqueue

\(\O(n)\)

dequeue

\(\O(1)\)

The time complexity for both enqueue and dequeue are \(\O(n)\) and \(\O(1)\), an obvious consequence because the native python list’s operations insert and pop are \(\O(n)\) and \(\O(1)\) respectively, so the result follows.

Space Complexity#

Space complexity: \(\O(n)\). The space required depends on the number of items stored in the list queue_items, so if queue_items stores up to \(n\) items, then space complexity is \(\O(n)\).

Further Readings#