Queue Data Structure

• Queue is a linear data structure
• it works on the principle First In First Out (FIFO).
• The first element insert into the queue is the first element to be delete
• Insertion can be done at rear end using rear pointer and deletions can be done at front end using front pointer
• It looks like open tube.
• The insertion operation is called append/enqueue operation
• The deletion operation is called as serve/dequeue operation.
• Enqueue operation on a full queue causes overflow.
• Dequeue operation on empty queue causes underflow.
• The initial value of the front and rear pointer is always –1
• The pointer front points to the starting end of the queue
• The pointer rear points to the rear end of the queue

For example

The fig 01 illustrates a queue containing three elements a, b and c. the element (a ) is at the front of the queue and c is at the rear of the queue. Fig 02 shows queue after deleting an element. Since elements may be deleted only from the front of the queue, (a) is removed and b is now at the front. Now fig 03 shows queue after inserting elements d and e , they must be inserted at the rear of the queue.

Operations of a queue:

There are two operations applied on queue they are 1 enqueue 2. dequeue. While performing enqueue operation check the queue is Full or not and while performing dequeue operation check the queue is empty or not.

Enqueue:

Insert an element into the queue is called Enqueue operation. Insertion can be done at rear end. At the time of insertion first check the queue is full or not. If the queue is full it generates an error message “queue if Full”.

Dequeue:

Delete an element from the queue is called Dequeue operation. Deletion can be done at front end. At the time of deleting first check the queue is empty or not. If the queue is empty it generates an error message “queue is empty”.

Assumptions:

rear, front are pointers , initial values are -1, -1

max_queue is the size of the queue

Q[ ] is an array

element is the element to be added or deleted

Algorithm for adding an element in to the queue (enqueue):

Step1: start

Step2: if (rear == max_queue - 1) then error “queue is full “go to step 5

Step3: else{ update front as front = front +1

Step4: put the element into the queue at rear as queue [rear] = element }

Step5: stop.

Algorithm for deleting an element from the queue (dequeue):

Step1: start

Step2: if (front == rear) then error “queue is empty” go to step5

Step3: else {update front as front = front +1

Step4: delete an element from front as element = queue [front]}

Step5: stop.

Applications of queue:

· Queues can be used to store the interrupts in the operating system

· It is used by an application program to store the incoming data

· Queue is used to process synchronization in Operating System

· Used for job scheduling

Drawbacks of a queue:

For each and every enqueue operation the queue is to be rearranged other wise even the queue is having an empty space it is not possible to utilize.