A queue is a special type of data structure that performs insertions at one end called the rear and deletions at the other end called the front.
A queue is a common example of a linear list or an ordered list where data can be inserted at and deleted from different ends.
A queue is a first in first out (FIFO) or last in last out (LILO) structure.
Queues are one of the most common data processing structures frequently used in most system software such as operating systems, network and database implementations, and other areas. Queues are very useful in time-sharing and distributed computer systems where many widely distributed users share the system simultaneously.
Queue as Abstract Data Type (ADT)
To realize a queue as an abstract data type (ADT), a suitable data structure for storing the elements in the queue and the functions operating on it are needed.
A minimal set of operations on a queue is as follows:
1. create()—creates an empty queue, Q
2. add(i,Q)—adds the element i to the rear end of the queue, Q and returns the new queue
3. delete(Q)—takes out an element from the front end of the queue and returns the resulting queue
4. getFront(Q)—returns the element that is at the front position of the queue
5. Is_Empty(Q)—returns true if the queue is empty; otherwise returns false.
Since a queue is a linear data structure, it can be implemented using either arrays or linked lists.
Implementation of Queue using Arrays
An array is not a suitable data structure for frequent insertion and deletion of data elements. Another drawback of arrays is that they use static memory allocation, and so they can store only a fixed number of elements.
The implementations of the various operations on the queue using arrays are:
Create
This operation should create an empty queue. Here max is the maximum initial size that is defined.
#define max 50
int Queue[max];
int Front = Rear = −1;
The two variables Front and Rear are initialized to represent an empty queue. The condition Front = Rear indicates an empty queue. As our array index ranges between 0 and (max − 1), the front and rear are initialized to -1.
Is_Empty
This operation checks whether the queue is empty or not. It is done by comparing the values of Front and Rear. If Front = Rear, then Is_Empty returns true, else returns false.
bool Is_Empty()
{
if(Front == Rear)
return 1;
else
return 0;
}
Is_Full
Before insertion of element, the queue must be checked for the Queue_Full state. When Rear points to the last location of the array, it indicates that the queue is full and there is no space to accommodate any more
elements.
bool Is_Full()
{
if(Rear == max − 1)
return 1;
else
return 0;
}
Add
This operation adds an element in the queue if it is not full. As Rear points to the last element of the queue, the new element is added at the (rear + 1)th location.
void Add(int Element)
{
if(Is_Full())
cout << “Error, Queue is full”;
else
Queue[++Rear] = Element;
}
Delete
This operation deletes an element from the front of the queue and sets Front to point to the next element. First Front has to be incremented then element is removed.
int Delete()
{
if(Is_Empty())
cout << “Sorry, queue is Empty”;
else
return(Queue[++Front]);
}
Code: Implementation of Queue using Array
class queue
{
private:
int Rear, Front;
int Queue[50];
int max;
int Size;
public:
queue()
{
Size = 0; max = 50;
Rear = Front = −1 ;
}
int Is_Empty();
int Is_Full();
void Add(int Element);
int Delete();
};
int queue :: Is_Empty()
{
if(Front == Rear)
return 1;
else
return 0;
}
int queue :: Is_Full()
{
if(Rear == max − 1)
return 1;
else
return 0;
}
void queue :: Add(int Element)
{
if(!Is_Full())
Queue[++Rear] = Element;
Size++;
}
int queue :: Delete()
{
if(!Is_Empty())
{
Size−−;
return(Queue[++Front]);
}
}
void main(void)
{
queue Q;
Q.Add(11);
Q.Add(12);
Q.Add(13);
cout << Q.Delete() << endl;
Q.Add(14);
cout << Q.Delete() << endl;
cout << Q.Delete() << endl;
cout << Q.Delete() << endl;
cout << Q.Delete() << endl;
Q.Add(15);
Q.Add(16);
cout << Q.Delete() << endl;
}
0 comments:
Post a Comment