# Priority Queue Tutorial

## What is Priority Queue?

Priority queue is a special type of queue, it store item into queue with associated priority. So that it does not support FIFO( First In First Out) structure.

It supports the following three operations:

1. InsertWithPriority: Insert an item to the queue with associated priority.
2. GetNext: remove the element from the queue which has highest priority and return it. It also know as PopElement() or GetMaximum.
3. PeekAtNext(optional): Get the item with highest priority without removing it.

#### Priority Queue Implementation with all above queue operations

```
#include <stdio.h>
#define MAX 5

//Declaration of priority queue
typedef struct
{
int ele[MAX][MAX];
int count;
}PQueue;

//Initialize priority queue
void init(PQueue *q)
{
int i=0;
q->count = 0;

//All priority value set to -1
for( i = 0; i < MAX ; i++ )
{
q->ele[i][1] = -1 ;
}
}

//Insert item with priority in queue
void insertWithPriority(PQueue *q, int priority, int item )
{
int i = 0;
if( q->count == MAX )
{
printf("\nPriority Queue is overflow");
return;
}

for ( i = 0; i < MAX; i++ )
{
if( q->ele[i][1] == -1)
break;
}

q->ele[i][0] = item;
q->ele[i][1] = priority;

q->count++;
printf("\nInserted item is : %d",item);
}

//Remove & get element with highest priority in queue
int GetNext(PQueue *q, int *item)
{
int i = 0,max,pos=0;

if( q->count == 0 )
{
printf("\nPriority Queue is underflow");
return -1;
}

max = q->ele[0][1];
for ( i = 1; i < MAX; i++ )
{
if( max < q->ele[i][1] )
{
pos = i;
max = q->ele[i][1];
}
}

*item = q->ele[pos][0];
q->ele[pos][1] = -1;

q->count--;
return 0;
}

//Get element with highest priority without removing it from queue
int PeekAtNext(PQueue *q, int *item)
{
int i = 0,max,pos=0;

if( q->count == 0 )
{
printf("\nPriority Queue is underflow");
return -1;
}

max = q->ele[0][1];
for ( i = 1; i < MAX; i++ )
{
if( max < q->ele[i][1] )
{
pos = i;
max = q->ele[i][1];
}
}

*item = q->ele[pos][0];

return 0;
}

int main()
{
int item;
PQueue q;

init( &q );

insertWithPriority( &q, 1, 10 );
insertWithPriority( &q, 2, 20 );
insertWithPriority( &q, 3, 30 );
insertWithPriority( &q, 4, 40 );
insertWithPriority( &q, 5, 50 );
insertWithPriority( &q, 6, 60 );

if( PeekAtNext( &q, &item) == 0 )
printf("\nPeek Item : %d",item);

if( GetNext( &q, &item) == 0 )
printf("\nItem : %d",item);

if( PeekAtNext( &q, &item) == 0 )
printf("\nPeek Item : %d",item);

if( GetNext( &q, &item) == 0 )
printf("\nItem : %d",item);
if( GetNext( &q, &item) == 0 )
printf("\nItem : %d",item);

if( PeekAtNext( &q, &item) == 0 )
printf("\nPeek Item : %d",item);

if( GetNext( &q, &item) == 0 )
printf("\nItem : %d",item);
if( GetNext( &q, &item) == 0 )
printf("\nItem : %d",item);
if( GetNext( &q, &item) == 0 )
printf("\nItem : %d",item);

printf("\n");

return 0;
}
```
```    Inserted item is : 10
Inserted item is : 20
Inserted item is : 30
Inserted item is : 40
Inserted item is : 50
Priority Queue is overflow
Peek Item : 50
Item : 50
Peek Item : 40
Item : 40
Item : 30
Peek Item : 20
Item : 20
Item : 10
Priority Queue is underflow
```
```
#include <iostream>

using namespace std;
#define MAX 5

//Declaration of priority queue
class PQueue
{
private:
int ele[MAX][MAX];
int count;

public:
PQueue();
void insertWithPriority(int priority, int item );
int GetNext(int *item);
int PeekAtNext(int *item);

};

//Initialize priority queue
PQueue:: PQueue()
{
int i=0;
count = 0;

//All priority value set to -1
for( i = 0; i < MAX ; i++ )
{
ele[i][1] = -1 ;
}
}

//Insert item with priority in queue
void PQueue:: insertWithPriority(int priority, int item )
{
int i = 0;
if( count == MAX )
{
cout<< "\nPriority Queue is overflow";
return;
}

for ( i = 0; i < MAX; i++ )
{
if( ele[i][1] == -1)
break;
}

ele[i][0] = item;
ele[i][1] = priority;

count++;
cout<<"\nInserted item is : "<< item;
}

//Remove & get element with highest priority in queue
int PQueue:: GetNext(int *item)
{
int i = 0,max,pos=0;

if( count == 0 )
{
cout<<"\nPriority Queue is underflow";
return -1;
}

max = ele[0][1];
for ( i = 1; i < MAX; i++ )
{
if( max < ele[i][1] )
{
pos = i;
max = ele[i][1];
}
}

*item = ele[pos][0];
ele[pos][1] = -1;

count--;
return 0;
}

//Get element with highest priority without removing it from queue
int PQueue:: PeekAtNext(int *item)
{
int i = 0,max,pos=0;

if( count == 0 )
{
cout<<"\nPriority Queue is underflow";
return -1;
}

max = ele[0][1];
for ( i = 1; i < MAX; i++ )
{
if( max < ele[i][1] )
{
pos = i;
max = ele[i][1];
}
}

*item = ele[pos][0];

return 0;
}

int main()
{
int item;
PQueue q = PQueue();

q.insertWithPriority( 1, 10 );
q.insertWithPriority( 2, 20 );
q.insertWithPriority( 3, 30 );
q.insertWithPriority( 4, 40 );
q.insertWithPriority( 5, 50 );
q.insertWithPriority( 6, 60 );

if( q.PeekAtNext( &item) == 0 )
cout<<"\nPeek Item : "<< item;

if( q.GetNext( &item) == 0 )
cout<<"\nItem : "<< item;

if( q.PeekAtNext( &item) == 0 )
cout<<"\nPeek Item : "<< item;

if( q.GetNext( &item) == 0 )
cout<<"\nItem : "<< item;
if( q.GetNext( &item) == 0 )
cout<<"\nItem : "<< item;

if( q.PeekAtNext( &item) == 0 )
cout<<"\nPeek Item : "<< item;

if( q.GetNext( &item) == 0 )
cout<<"\nItem : "<< item;
if( q.GetNext( &item) == 0 )
cout<<"\nItem : "<< item;
if( q.GetNext( &item) == 0 )
cout<<"\nItem : "<< item;

cout<< endl;

return 0;
}

```
```    Inserted item is : 10
Inserted item is : 20
Inserted item is : 30
Inserted item is : 40
Inserted item is : 50
Priority Queue is overflow
Peek Item : 50
Item : 50
Peek Item : 40
Item : 40
Item : 30
Peek Item : 20
Item : 20
Item : 10
Priority Queue is underflow
```