Data Structure

# Implementation of Queues

1. Implementation using Array (Static Queue)
2. Implementation using Linked List (Dynamic Queue)

# Structure of Queue

Structure of Queue.
#define max 5
struct queue
{
int data[max];
int front, rear ;
}

# Algorithm for Insertion in Queue

Insert ( )
1. If (REAR == N) Then [Check for overflow]
2.		Print: Overflow
3. Else
4.		If (FRONT and REAR == 0) Then [Check if QUEUE is empty]
(a) Set FRONT = 1
(b) Set REAR = 1
5. 			Else
6. 				Set REAR = REAR + 1 [Increment REAR by 1]
[End of Step 4 If]
7. 			QUEUE[REAR] = ITEM
8. 			Print: ITEM inserted
[End of Step 1 If]
9.	Exit

# Algorithm for Deletion in Queue

Delete ( )
1. If (FRONT == 0) Then [Check for underflow]
2. 		Print: Underflow
3. Else
4. 		ITEM = QUEUE[FRONT]
5. 		If (FRONT == REAR) Then [Check if only one element is left]
(a) Set FRONT = 0
(b) Set REAR = 0
6. 		Else
7. 			Set FRONT = FRONT + 1 [Increment FRONT by 1]
[End of Step 5 If]
8. 		Print: ITEM deleted
[End of Step 1 If]
9. Exit

# Array implementation of Queue

In this type of implementation we use array structure for data storage.
#include<stdio.h>
#include<conio.h>
#define SIZE 5

int front=-1;
int rear=-1;
int q[SIZE];

void insert();
void del();
void display();

void main()
{
int choice;
clrscr();
do
{
clrscr();
printf("\n 1. Insert");
printf("\n 2. Delete");
printf("\n 3. Display ");
printf("\n 4. Exit");

scanf("%d",&choice);

switch(choice)
{
case 1:
insert();
display();
getch();
break;
case 2:
del();
display();
getch();
break;
case 3:
display();
getch();
break;
case 4:
printf("End of Program....!!!!");
getch();
exit(0);
}
}while(choice!=4);
}

void insert()
{
int no;
printf("\n Enter No.:");
scanf("%d",&no);

if(rear < SIZE-1)
{
q[++rear]=no;
if(front==-1)
front=0;// front=front+1;
}
else
{
printf("\n Queue overflow");
}
}

void del()
{
if(front==-1)
{
printf("\nQueue Underflow");
return;
}
else
{
printf("\nDeleted Item:-->%d\n",q[front]);
}
if(front==rear)
{
front=-1;
rear=-1;
}
else
{
front=front+1;
}
}

void display()
{
int i;
if(front==-1)
{
printf("\nQueue is empty....");
return;
}
for(i=front;i<=rear;i++)
printf("\t%d",q[i]);
}