*****************
Topic 10 - Queues
*****************

*  The queues ADT is a list, so we have the same operations:

   *  Enqueue (Insert)
   *  Dequeue (Delete)

*  However, the idea of the queues is to implement a FIFO strategy.

   *  FIFO for First In First Out.

*  The insertion is done at the beginning of the list and the deletion at the end.


.. figure:: ../img/topic10/queue_model.png
    :align: center


Array Implementation of Queues
==============================

*  All operations in a queue are fast :math:`O(1)`.
*  The idea:

   *  We are using an array to implement it.
   *  We keep the positions :code:`front` and :code:`back`.
   *  We also keep the number of elements in the queue. :code:`currentSize`.


.. admonition:: Example

    .. figure:: ../img/topic10/array_queue.png
        :align: center


Enqueue
-------

*  Consider that you want to **enqueue** an element :code:`x`.
*  We need to:

   *  Increment :code:`currentSize`
   *  Increment :code:`back`
   *  Set :code:`array[back] = x`

Dequeue
-------

*  Consider that you want to **dequeue** an element :code:`x`.
*  We need to:

   *  Return :code:`array[front]`
   *  Decrement :code:`currentSize`
   *  Increment :code:`front`

Limits of Implementation?
-------------------------

*  If you paid attention, you can see there is an issue.
*  We don't change the size of the table.
*  After a few operations :code:`front` and :code:`back` reach the end of the array.

.. admonition:: Activity
    :class: warning

    *  Discuss how can we could solve this problem.
    *  Try on a small array.

Example
-------

*  We will consider the following initial state.
*  We will enqueue 1 and 3, then dequeue 4 times.

.. figure:: ../img/topic10/queue_example.png
    :align: center

*  Done in class.