QUEUE AND its APPLICATIONS

-by Kriti Rai (1CR16IS044)

A queue is an ordered collection of items where an item is inserted at one end called the “REAR” and an existing item is removed at the other end called the “FRONT”. Queue is a structure in which whatever goes first comes first in short we call as FIFO structure which is “First In First Out”.

EXAMPLE of a QUEUE:

A line of students in the food court of a canteen, new additions to the line are made to the back of the queue, while removal happens at the front.

TYPES OF QUEUES:

It can be of four types:-

1. Simple queue
2. Circular queue
3. Priority queue
4. Dequeue (double ended queue)

SIMPLE QUEUE: In simple queue insertion occurs at the rear end of the list and deletion occurs at the front end of the list.

Concept of circular Queue:

Suppose we want to insert an element ‘ITEM’ into a queue at the time when an element occupies last index of the array that is when rear is N-1 (N=size of  linear array), one way is to move entire Queue to the beginning of the array changing FRONT and REAR accordingly this is very expansive.

OPERATIONS ON QUEUE:

Queue () – Creates a new queue that is empty. It needs no parameters and returns the empty queue.

Enqueue (item) – Adds a new item to the rear of the queue. It needs the item and returns nothing. This operation is generally called as push.
Dequeue () – Removes the front item from the queue. It needs no parameter and returns the item. The queue is modified. This operation is generally called as pop.

is_empty () – Tests to see whether the queue is empty. It needs no parameters and returns a Boolean value.

Size – Returns the number of items in the queue. It needs no parameter and returns an integer.

Memory representation of a queue using arrays:

Queue is represented in memory linear array. Let Queue be a linear queue. Two pointers variable called FRONT and REAR are maintained. The pointer variable FRONT contains the location of the element to be removed and the pointer variable REAR contains location of the last element inserted.

Conditions:

• FRONT=NULL indicates that the queue is empty.
• REAR=N indicates that queue is full.

APPLICATIONS:

1. Queue is most often used in a scenario where there is a shadow resource that is supposed to serve some request but this resource can handle only one request at a time. In such a scenario it makes most sense to queue up the request that comes first get served first.
2. PRINTER SERVER ROUTINES: Let us say we have a printer shared in our network and any machine connected to the network can send a print request to the printer, but the printer can serve only one request at a time which means it can print only one document at the time. So if a request comes when it is busy it can’t be like, “I am busy, send the requests later”, because that would be really rude of the printer. What really happens is that the program that manages the printer puts the printer request in a queue. As long as there is something in the queue, the printer keeps picking up a request from the front of the queue and serves it.
3. In a multitasking operating system, the CPU cannot run all the tasks at once, so the tasks must be batched up and then scheduled according to some policy. Again a queue might be a suitable option in this case.
4. Operating systems often maintain a queue of processes that are ready to be executed or that are waiting for a particular event to occur.
5. Handling of interrupts in real time systems. The interrupts are handled in the same order as they arrive i.e. ‘first come first served’.