Tuesday, 19 December 2017

Write C++ code to implement Queue ADT and test its features.

A Queue is an ordered list in which all insertion takes place at one end and all deletions take place at the opposite end. Since the first element removed is the first element inserted, queues are also known as First In First Out (FIFO) lists. The end at which insertions are taken place is called ‘rear’ and the end at which deletions take place is called ’front’.
In a standard queue data structure re-buffering problem occurs for each dequeue operation. That means, the queue tells it is full even though there are empty locations. This problem is solved by joining the front and rear ends of the queue to make the queue as a circular queue. When rear == MaxSize-1 the next element is entered at queue[0] in case that is empty. 
Queues are frequently used in computer programming, and one example is the creation of a job queue by an Operating System. If the OS does not use priorities, the jobs are processed in the order they enter the system.

Algorithm:
template<class T>
class Queue
{
private:
int front,rear;
T *queue;
int qsize;
public:
Queue(int size); //Constructor.
int isFull(); //return 1 for Full,0 for not Full.
int isEmpty(); //return 1 for Empty, 0 for not Empty
void Insert(T item); //Inserts an item at the rear of queue.
T Delete(); //Deletes an item at the front of queue.
}
//constructor
template<class T>
Queue<T>:: Queue(int size)
{
qsize=size;
queue=new T[qsize];
front=rear= -1;
}
// isFull() function
template<class T>
int Queue<T>::isFull()
{
if((rear+1)%qsize==front)
return 1;
else
return 0;
}
//isEmpty()function
template<class T>
int Queue<T>::isEmpty();
{
if(front==rear || front == -1)
return 1;
else
return 0;
}
//Insert () function
template<class T>
void Queue<T>::Insert(T item)
{
if(isFull())
Queue is Full;
else if (front = -1)
{
front = 0;
rear = 0;
}
else
rear=(rear+1)%qsize;
queue[rear]=item;
}
//Delete () function
template<class T>
T Queue<T>::Delete()
{
If(isEmpty())
{
Queue is Empty;
return NULL;
}
T x=queue[front];
front=(front+1)%qsize;
return x;
}


Thanks
Mukesh Rajput

No comments:

Post a Comment

Thanks
Mukesh Rajput