Double Ended Queue#
The Queue Abstract Data Type#
Same idea as Queue, but now you can insert people in the front of the queue (cut-queue 😂) and
also remove people from the end of the queue (people leaving cause queue too long?).
Note possible confusion in the method names below, as add_front really means insert an item
at the front the queue but it uses append because we treat the rear of a list as the “front”.
Python Implementation#
from __future__ import annotations
from typing import Generic, TypeVar, List
T = TypeVar("T")
class DeQueueList(Generic[T]):
"""Creates a double-ended 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 dequeue."""
return len(self.queue_items)
@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 add_front(self, item: T) -> None:
"""Insert an item at the front of the queue.
Args:
item (T): The current item to be added.
"""
self.queue_items.append(item)
def add_rear(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 remove_front(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()
def remove_rear(self) -> T:
"""Pop an item from the end of the queue.
Raises:
(Exception): If queue is empty.
Returns:
(T): The item at the end of the queue.
"""
if self.is_empty():
raise Exception("Queue is empty")
return self.queue_items.pop(0)
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 = DeQueueList()
print(q.is_empty())
q.add_rear(4)
q.add_rear("dog")
q.add_front("cat")
q.add_front(True)
print(q.size)
print(q.is_empty())
q.add_rear(8.4)
print(q.remove_rear())
print(q.remove_front())
True
4
False
8.4
True
Time Complexity#
Operations |
Time Complexity |
|---|---|
|
\(\O(n)\) |
|
\(\O(1)\) |
|
\(\O(n)\) |
|
\(\O(1)\) |
With reference to the previous section on Concept, the time complexity for both add_rear (enqueue)
and dequeue (remove_front) 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. The same applies to add_front and remove_rear.
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)\).