Queue

Introduction

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

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

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.

 

Resources

Link List (can use to implement a queue)

Exam Questions