Queue introduction

QUEUE

A queue is a data structure used for storing data (similar to Linked Lists and Stacks). In the queue, the order in which data arrives is important. In general, a queue is a line of people or things waiting to be served in sequential order starting at the beginning of the line or sequence.

Definition: A queue is an ordered list in which insertions are done at one end (rear) and deletions are done at another end (front). The first element to be inserted is the first one to be deleted. Hence, it is called First in First out (FIFO) or Last in Last out (LILO) list. Similar to Stacks, special names are given to the two changes that can be made to a queue. When an element is inserted in a queue, the concept is called EnQueue, and when an element is removed from the queue, the concept is called DeQueue. DeQueueing an empty queue is called underflow and EnQueuing an element in a full queue is called overflow. Generally, we treat them as exceptions. As an example, consider the snapshot of the queue.

A queue is an ordered list in which insertions are done at one end (rear) and deletions are done at other ends (front). The first element to be inserted is the first one to be deleted. Hence, it is called First In First Out (FIFO) or Last In Last Out (LILO) list.

HOW ARE THEY USED: The concept of a queue can be explained by observing a line at a reservation counter. When we enter the line we stand at the end of the line and the person who is at the front of the line is the one who will be served next. He will exit the queue and be served. As this happens, the next person will come at the head of the line, will exit the queue, and will be served. As each person at the head of the line keeps exiting the queue, we move towards the head of the line. Finally, we will reach the head of the line and we will exit the queue and be served. This behavior is very useful in cases where there is a need to maintain the order of arrival.

QUEUE ADT

Main Queue Operations:

• enQueue(int data): Inserts an element at the end of the queue

• deQueue(): Removes and returns the element at the front of the queue.

Auxiliary Queue Operations

• int Front(): Returns the element at the front without removing it

• int QueueSize(): Returns the number of elements stored in the queue
• int IsEmptyQueue(): Indicates whether no elements are stored in the queue or not

Queue Functioning

APPLICATIONS:

• Operating systems schedule jobs (with equal priority) in the order of arrival (e.e a print queue).

• Simulation of real-world queues such as lines at a ticket counter, or any other first-come-first-served scenario requires a queue.

• Multiprogramming.

• Asynchronous data transfer (file IO, pipes, sockets).

• Waiting times for a customer at a call center.

• Determining the number of cashiers to have at a supermarket.

• The consumer who comes first to a shop will be served first. 

• CPU task scheduling and disk scheduling.

• Waiting list of tickets in case of bus and train tickets.