Queues and First In First Out

Queues

In the last post, the stack data structure was explored. A stack is a Last In First out data structure. The stack post is a useful prerequisite for this queue tutorial.

The opposite to a ‘last in first out’ data structure is a ‘first in first out’ (FIFO) data structure. This means that elements can only be removed if they are the oldest item in the structure, in other words – they are at the front of the queue. We call these data structures queues.

Adding and removing from the queue

Real-Life Examples of a Queue

A queue is not a difficult concept to grasp as they are so widely used in the real world. Examples of where queues are used include:

Queuing for an Attraction

Socially, it is common to queue for an attraction such as an ATM, bus or theme park ride. People do this as there is an understanding that it leaves each person with a ‘fair’ time to wait for something they want. It is an understanding that people join at the back of the queue and when someone arrives at the front, they are next.

System Implementation of Queues

Similar to queuing in real life, systems might also implement queues to improve the ‘equality’ for their targets. These targets being people, tasks or otherwise.

One example might be how a web server deals with requests for a webpage. If they web-server gets many requests at once it will try to serve the first request that arrived first.

Operations for a Queue

Similar to many other data structures, the queue needs a method to both to introduce new data and remove old data. These two processes are called enqueue and dequeue respectively.

Enqueue

The enqueue operation is responsible for adding new elements at the back of the queue. An example implementation of the Enqueue method in an array-based implementation can be found below.

Code

public void enqueue(int data) { if (capacity == rear) { Console.Write("Queue is at full capacity"); return; } else { queuerear = data; rear++; } return; }