myqueue.py

"""CSC148 Lab 4: Abstract Data Types
Department of Computer Science,
University of Toronto

=== Module Description ===
In this module, you will develop an implementation of the Queue ADT.
It will be helpful to review the stack implementation from lecture.
"""
from typing import Any
from python_ta.contracts import check_contracts
from collections import deque


# TODO: Task 1
#  Implement this class! Note that you'll need at least one private
#  attribute to store items.
#  A Python list should be used, with items being added to the END of the
#  list when enqueuing.
@check_contracts
class Queue:
    """A first-in-first-out (FIFO) queue of items.

    Stores data in a first-in, first-out order. When removing an item from the
    queue, the first item added is the one that is removed.
    """
    # Private Attributes: 

    _queue_storage: list[Any]

    def __init__(self) -> None:
        """Initialize a new empty queue.""" 
        self._queue_storage = []

    def is_empty(self) -> bool:
        """Return whether this queue contains no items.

        >>> q = Queue()
        >>> q.is_empty()
        True
        >>> q.enqueue('hello')
        >>> q.is_empty()
        False
        """ 
        return self._queue_storage == []
  
        

    def enqueue(self, item: Any) -> None:
        """Add <item> to the back of this queue.
        """

        self._queue_storage.append(item)

    def dequeue(self) -> Any | None:
        """Remove and return the item at the front of this queue.

        Return None if this Queue is empty.
        (We illustrate a different mechanism for handling an erroneous case.)

        >>> q = Queue()
        >>> q.enqueue('hello')
        >>> q.enqueue('goodbye')
        >>> q.dequeue()
        'hello'
        """

        if self._queue_storage == []: 
            return None
        else: 
            return self._queue_storage.pop(0)


# TODO: Task 2
#  Implement this class! QueueOpposite is similar to Queue, except items
#  should be added to the START of the list when enqueueing.
class QueueOpposite:
    """A first-in-first-out (FIFO) queue of items.

    Stores data in a first-in, first-out order. When removing an item from the
    queue, the first item added is the one that is removed.
    """
    # Private Attributes: 

    _queue_opposite_storage: list[Any]

    def __init__(self) -> None:
        """Initialize a new empty queue.""" 

        self._queue_opposite_storage = []

    def is_empty(self) -> bool:
        """Return whether this queue contains no items.

        >>> q = QueueOpposite()
        >>> q.is_empty()
        True
        >>> q.enqueue('hello')
        >>> q.is_empty()
        False
        """
        return self._queue_opposite_storage == []

    def enqueue(self, item: Any) -> None:
        """Add <item> to the back of this queue.
        """ 

        self._queue_opposite_storage.insert(0, item)

    def dequeue(self) -> Any | None:
        """Remove and return the item at the front of this queue.

        Return None if this Queue is empty.
        (We illustrate a different mechanism for handling an erroneous case.)

        >>> q = QueueOpposite()
        >>> q.enqueue('hello')
        >>> q.enqueue('goodbye')
        >>> q.dequeue()
        'hello'
        """ 
        if self._queue_opposite_storage == []:
            return None 
        else: 
            return self._queue_opposite_storage.pop()



# TODO: Task 3
#  Implement this class!
#  Instead of using a Python list, QueueDeque should use the Python "deque"
#  object.
#  See below for documentation on the deque class:
#  https://docs.python.org/3/library/collections.html#collections.deque
class QueueDeque:
    """A first-in-first-out (FIFO) queue of items.

    Stores data in a first-in, first-out order. When removing an item from the
    queue, the first item added is the one that is removed.
    """
    # Private Attributes: 

    _queue_deque_object_storage: deque[Any]

    def __init__(self) -> None:
        """Initialize a new empty queue.""" 

        self._queue_deque_object_storage = deque()


    def is_empty(self) -> bool:
        """Return whether this queue contains no items.

        >>> q = QueueDeque()
        >>> q.is_empty()
        True
        >>> q.enqueue('hello')
        >>> q.is_empty()
        False
        """ 

        return len(self._queue_deque_object_storage) == 0

    def enqueue(self, item: Any) -> None:
        """Add <item> to the back of this queue.
        """

        return self._queue_deque_object_storage.append(item)

    def dequeue(self) -> Any | None:
        """Remove and return the item at the front of this queue.

        Return None if this Queue is empty.
        (We illustrate a different mechanism for handling an erroneous case.)

        >>> q = QueueDeque()
        >>> q.enqueue('hello')
        >>> q.enqueue('goodbye')
        >>> q.dequeue()
        'hello'
        """ 

        if len(self._queue_deque_object_storage) == 0: 
            return None 
        else: 
           return self._queue_deque_object_storage.popleft()


if __name__ == '__main__':
    import doctest

    doctest.testmod(verbose=True)