Introduction to Queues
A queue is a data structure that operates on a First In First Out (FIFO) principle.
They work just like in real life queues where:
- new items are added to the rear of the queue (ENQUE)
- when an items is removed the item at the front of the queue is removed first (DEQUE)
Linear Queue
A linear queue works exactly as in real life. When you go to stand in the queue you just stand at the rear, but when the person at the front of the queue has finished being served everyone else in the queue has to shuffle forward a little bit. This is highly inefficient as each item in the array holding the queue has to be moved along by one position. If your queue is 1 million items long you will need to move 1 million items!
We need a more efficient solution and for this we can use a circular queue.
Circular Queue
In a circular queue, you keep track of the index of the front and rear of the queue.
- Each time you add a new item to the queue, you add it to the new empty space and then you increment the rear index by one.
- Each time you remove an item from the front of the queue you remove it and then increment the front index by one.
- If either index is equal to the length of the array then you need to reset that index to zero.
Queue Methods
Here are the standard queue methods:
Enqueue
This is where an item is added to the rear of the queue
Dequeue
This is where an item is removed from the front of the queue and returned to the program.
Peek
This is where the item at the front is returned, without removing the item from the queue.