Home »
Data Structure
Linear Queue Tutorial
What Linear Queue?
- It is a linear data structure.
- It is considered as sequence of items.
- It supports FIFO (First In First Out) property.
-
It has three components:
- A Container of items that contains elements of queue.
- A pointer front that points the first item of the queue.
- A pointer rear that points the last item of the queue.
- Insertion is performed from REAR end.
- Deletion is performed from FRONT end.
- Insertion operation is also known as ENQUEUE in queue.
Implementation of Queue
Queue can be implementing by two ways:
- Array or contiguous implementation.
- Linked List implementation.
Array Implementation of Queue
In Array implementation FRONT pointer initialized with 0 and REAR initialized with -1.
Consider the implementation :- If there is 5 items in a Queue
Note: In case of empty queue, front is one position ahead of rear : FRONT = REAR + 1;
Drawback of Linear Queue
The linear queue suffers from serious drawback that performing some operations, we can not insert items into queue, even if there is space in the queue. Suppose we have queue of 5 elements and we insert 5 items into queue, and then delete some items, then queue has space, but at that condition we can not insert items into queue.
There are five operations possible on a queue:
- Initialize operation
- Addition or insertion operation.
- Deletion operation.
- Is_full check.
- Is_empty check.
Algorithms
In algorithm implementation first item of queue starts from 1, and in program implementation first item will be start from 0.
- INIT(QUEUE,FRONT,REAR)
- INSERT-ITEM(QUEUE,FRONT,REAR,MAX,ITEM)
- REMOVE-ITEM(QUEUE,FRONT,REAR,ITEM)
- FULL-CHECK(QUEUE,FRONT,REAR,MAX,FULL)
- EMPTY-CHECK(QUEUE,FRONT,REAR,EMPTY)
INIT(QUEUE,FRONT,REAR)
This algorithm is used to intialize a QUEUE,FRONT,
and REAR.
1. FRONT := 1;
2. REAR := 0;
3. Return;
INSERT-ITEM(QUEUE,FRONT,REAR,MAX,ITEM)
This algorithm is used to add or insert item to QUEUE.
1. If (REAR = MAX) then
a. Display “Queue overflow”;
b. Return;
2. Otherwise
a. REAR := REAR + 1;
b. QUEUE(REAR) := ITEM;
3. Return;
REMOVE-ITEM(QUEUE,FRONT,REAR,ITEM)
This algorithm is used to delete an item from QUEUE.
1. If (FRONT = REAR + 1) then
a. Display “Queue underflow”;
b. Return;
2. Otherwise
a. ITEM := QUEUE(FRONT);
b. FRONT := FRONT + 1;
3. Return;
EMPTY-CHECK(QUEUE,FRONT,REAR,EMPTY)
This algorithm is used to check whether
a QUEUE is EMPTY or not.
1. If (FRONT = REAR + 1) then
a. EMPTY := true;
2. Otherwise
a. EMPTY := false;
3. Return;
FULL-CHECK(QUEUE,FRONT,REAR,MAX,FULL)
This algorithm is used to check whether
a QUEUE is full or not.
1. If ( REAR = MAX ) then
a. FULL := true;
2. Otherwise
a. FULL := false;
3. Return;
Declaration of Linear Queue
#define MAX 5
/*Declaration of Queue*/
typedef struct queue
{
int front ;
int rear ;
int ele[MAX] ;
}Queue;
#define MAX 5
class Queue
{
private:
int front,rear;
int ele[MAX];
public:
//To Initalize queue
Queue()
{
front = 0;
rear = -1;
}
int isFull();
int isEmpty();
void insertQueue(int item);
int deleteQueue(int *item);
};
Linear Queue Implementation for all above queue operations
#include <stdio.h>
#define MAX 5
//Declaration of Queue
typedef struct queue
{
int front ;
int rear ;
int ele[MAX] ;
}Queue;
//Intialze Queue
void init(Queue *q)
{
q->rear = -1;
q->front = 0;
}
//To check Queue is full or not
int isFull(Queue *q)
{
int full=0;
if( q->rear == MAX -1)
full = 1;
return full;
}
//To check Queue is empty or not
int isEmpty(Queue *q)
{
int empty=0;
if( q->front == q->rear+1 )
empty = 1;
return empty;
}
//Insert item into queue
void insertQueue(Queue *q,int item)
{
if( isFull(q) )
{
printf("\nQueue Overflow");
return;
}
q->ele[++(q->rear)] = item;
printf("\nInserted item : %d",item);
}
//Delete item from queue
int deleteQueue(Queue *q, int * item)
{
if( isEmpty(q) )
{
printf("\nQueue Underflow");
return -1;
}
*item = q->ele[(q->front)++];
return 0;
}
int main()
{
int item = 0;
Queue q;
init(&q);
insertQueue(&q,10);
insertQueue(&q,20);
insertQueue(&q,30);
insertQueue(&q,40);
insertQueue(&q,50);
insertQueue(&q,60);
if( deleteQueue( &q, &item ) == 0 )
printf("\nDeleted item : %d",item);
if( deleteQueue( &q, &item ) == 0 )
printf("\nDeleted item : %d",item);
if( deleteQueue( &q, &item ) == 0 )
printf("\nDeleted item : %d",item);
if( deleteQueue( &q, &item ) == 0 )
printf("\nDeleted item : %d",item);
if( deleteQueue( &q, &item ) == 0 )
printf("\nDeleted item : %d",item);
if( deleteQueue( &q, &item ) == 0 )
printf("\nDeleted item : %d",item);
printf("\n");
return 0;
}
Inserted item : 10
Inserted item : 20
Inserted item : 30
Inserted item : 40
Inserted item : 50
Queue Overflow
Deleted item : 10
Deleted item : 20
Deleted item : 30
Deleted item : 40
Deleted item : 50
Queue Underflow
#include <iostream>
using namespace std;
#define MAX 5
class Queue
{
private:
int front,rear;
int ele[MAX];
public:
Queue() //To Initalize queue
{
front = 0;
rear = -1;
}
int isFull();
int isEmpty();
void insertQueue(int item);
int deleteQueue(int *item);
};
//To check queue is full or not
int Queue::isFull()
{
int full = 0 ;
if( rear == MAX-1 )
full = 1;
return full;
}
//To check queue is empty or not
int Queue::isEmpty()
{
int empty = 0 ;
if( front == rear + 1 )
empty = 1;
return empty;
}
//Insert Item into queue
void Queue:: insertQueue(int item)
{
if( isFull() )
{
cout<<"\nQueue OverFlow" << endl;
return;
}
ele[++rear]=item;
cout<<"\ninserted Value :" << item;
}
//delete item from queue
int Queue:: deleteQueue(int *item)
{
if( isEmpty() )
{
cout<<"\nQueue Underflow" << endl;
return -1;
}
*item = ele[front++];
return 0;
}
int main()
{
int item=0;
Queue q = Queue();
q.insertQueue(10);
q.insertQueue(20);
q.insertQueue(30);
q.insertQueue(40);
q.insertQueue(50);
q.insertQueue(60);
if(q.deleteQueue( &item)==0)
cout<<"\nDeleted item : "<< item;
if(q.deleteQueue( &item)==0)
cout<<"\nDeleted item : "<< item;
if(q.deleteQueue( &item)==0)
cout<<"\nDeleted item : "<< item;
if(q.deleteQueue( &item)==0)
cout<<"\nDeleted item : "<< item;
if(q.deleteQueue( &item)==0)
cout<<"\nDeleted item : "<< item;
if(q.deleteQueue( &item)==0)
cout<<"\nDeleted item : "<< item;
cout<< endl;
return 0;
}
inserted Value :10
inserted Value :20
inserted Value :30
inserted Value :40
inserted Value :50
Queue OverFlow
Deleted item : 10
Deleted item : 20
Deleted item : 30
Deleted item : 40
Deleted item : 50
Queue Underflow
Note: The drawback of queue can be solved with the help of circular queue.