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.
![_images/queue_model.png](_images/queue_model.png)
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
andback
.We also keep the number of elements in the queue.
currentSize
.
Example
![_images/array_queue.png](_images/array_queue.png)
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
andback
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.
![_images/queue_example.png](_images/queue_example.png)
Done in class.