Queues

4.1 INTRODUCTION

A queue is a non-primitive linear data structure .It is an homogeneous collection of elements in which new elements are added at one end called the Rear end , and the existing elements are deleted from other end called the Front end.

4.2 OPERATION ON QUEUES

The basic operations that can be performed on queue are:
To insert an element in the queue.
To delete an element from the queue.

4.3 DEQUEUES

It is homogeneous list of elements in which insertion and deletion operations are performed from both the ends.

4.4 Operations on Dequeue

1. Insertion of an element at the REAR end of the queue.
2. Deletion of an element from the FRONT end of the queue.
3. Insertion of an element at the FRONT end of the queue.
4. Deletion of an element from the REAR end of the queue

For an input-restricted deque only the operations specified in 1, 2, 3 and 4 are valid. And for out- restricted deque only the operations specified in 1, 2, 3 are valid.


4.5Application of arrays

1. Round robin technique for processor scheduling is implemented using queues.
2. All types of customer service (like railway ticket reservation) center software’s are designed using queues to store customers information.
3. Printer server routines are designed using queues.


Experiment 7

Aim- Write a program to perform add and delete operations in the linear queue

Algorithm (Insertion)
Let QUEUE be the array of some specified size say MAXSIZE, then the insertion algorithm will be as given below.While implementing a queue using arrays we must check underflow and overflow conditions for queue.

1. Initialize Front =0 and Rear = -1
2. If Rear b>= MAXSIZE [Check overflow condition]
Write Queue Overflow and return
Else
Set Rear = Rear + 1
3. QUEUE[Rear] = Item
4. If Front = -1 [Set the front pointer]
5. Return.

Algorithm (Deletion)

1. [Check underflow condition]
If Front < 0
Print : Queue is Empty and return
Else :
Item = QUEUE[Front] [Remove Element from front]
3. [Find new value of front.]
If (Front= = Rear) [Checking for empty queue]
Set front=0 , Rear = -1 [Re- initialize the pointers]
Else:
Front = Front +1
4. Return

4.7VIVA VOICE

1.What is a queue?
2.What does ‘front’ and ‘rear’ of the queue?
3. What is the full form of DEQUEUE?
4. How is queue different from stack?
5. Distinguish between LIFO and FIFO.
6. What is full queue and empty queue condition
7. What is circular queue and how do you represent it?
8. What is Dequeue?
9. What is meant by priority queues?