Concept#
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 queueq
and call thisenqueue
and say thatq.enqueue(p1) -> q = [p1]
;Then, person 2
p2
came to queue, we place him into the queueq
usingenqueue
and say thatq.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 thereforep2
has to be slotted afterp1
, 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 thatq.dequeue()
, which returnsp1
and at the same time removep1
from the queue, so nowq = [p2]
. Notedequeue
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#
Operations |
Time Complexity |
---|---|
|
\(\O(n)\) |
|
\(\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)\).