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.

Array Implementation of Queues

• All operations in a queue are fast \(O(1)\).

• The idea:

  • We are using an array to implement it.

  • We keep the positions front and back.

  • We also keep the number of elements in the queue. currentSize.

Example

Enqueue

• Consider that you want to enqueue an element x.

• We need to:

  • Increment currentSize

  • Increment back

  • Set array[back] = x

Dequeue

• Consider that you want to dequeue an element x.

• We need to:

  • Return array[front]

  • Decrement currentSize

  • Increment 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 front and back reach the end of the array.

Activity

• 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.

• Done in class.