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;
}
No comments:
Post a Comment