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 most recently-added item is the one that is removed.

    >>> q = Queue()
    >>> q.is_empty()
    True
    >>> q.enqueue('hello')
    >>> q.is_empty()
    False
    >>> q.enqueue('goodbye')
    >>> q.dequeue()
    'hello'
    >>> q.dequeue()
    'goodbye'
    >>> q.is_empty()
    True
    """
    # Private Instance Attributes:
    #   - _items: The items stored in this queue. The front of the list represents
    #             the front of the queue.
    _items: list

    def __init__(self) -> None:
        """Initialize a new empty queue."""
        self._items = []  # This takes constant time (Theta(1))

    def is_empty(self) -> bool:
        """Return whether this queue contains no items.
        """
        return self._items == []  # This takes constant time (Theta(1)).

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

        # (Analysis) The list.append method takes constant time (Theta(1)).

        # VERSION 2 (insert at front)
        # self._items.insert(0, item)

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

        Preconditions:
            - not self.is_empty()
        """
        if self.is_empty():
            raise EmptyQueueError
        else:
            return self._items.pop(0)

        # (Analysis)
        # In general, list.pop takes Theta(n - i) time.
        # Here, i = 0, so this takes Theta(n) time.

        # VERSION 2 (remove from end
        # return self._items.pop()


class EmptyQueueError(Exception):
    """Exception raised when calling dequeue on an empty queue."""

    def __str__(self) -> str:
        """Return a string representation of this error."""
        return 'dequeue may not be called on an empty queue'