Queues can be easily represented using linear arrays. every queue has front and rear variables that point to the position from where deletions and insertions can be done
Operations on Queues
In Fig. 8.1, FRONT = 0 and REAR = 5. Suppose we want to add another element with value 45, then REAR would be incremented by 1 and the value would be stored at the position pointed by REAR. The queue after addition would be as shown in Fig. 8.2. Here, FRONT = 0 and REAR = 6. Every time a new element has to be added, we repeat the same procedure. If we want to delete an element from the queue, then the value of FRONT will be incremented. Deletions are done from only this end of the queue. The queue after deletion will be as shown in Fig. 8.3.
Algorithm to insert an element in a queue
Step 1: IF REAR = MAX-1
Write OVERFLOW
Goto step 4
[END OF IF]
Step 2: IF FRONT=-1 and REAR=-1
SET FRONT = REAR =
ELSE
SET REAR = REAR+1
[END OF IF]
Step 3: SET QUEUE[REAR] = NUM
Step 4: EXIT
Algorithm to delete an element from a queue
Step 1: IF FRONT = -1 OR FRONT > REAR
Write UNDERFLOW
ELSE
SET FRONT = FRONT+1
[END OF IF]
Step 2: EXIT
C program to implement a linear queue
#include <stdio.h>
#include <conio.h>
#define MAX 10 // Changing this value will change length of array
int queue[MAX];
int front = -1, rear = -1;
void insert(void);
int delete_element(void);
int peek(void);
void display(void);
int main()
{
int option, val;
do
{
printf(“\n\n ***** MAIN MENU *****”);
printf(“\n 1. Insert an element”);
printf(“\n 2. Delete an element”);
printf(“\n 3. Peek”);
printf(“\n 4. Display the queue”);
printf(“\n 5. EXIT”);
printf(“\n Enter your option : “);
scanf(“%d”, &option);
switch(option)
{
case 1:
insert();
break;
case 2:
val = delete_element();
if (val != -1)
printf(“\n The number deleted is : %d”, val);
break;
case 3:
val = peek();
if (val != -1)
printf(“\n The first value in queue is : %d”, val);
break;
case 4:
display();
break;
}
}while(option != 5);
getch();
return 0;
}
void insert()
{
int num;
printf(“\n Enter the number to be inserted in the queue : “);
scanf(“%d”, &num);
if(rear == MAX-1)
printf(“\n OVERFLOW”);
else if(front == -1 && rear == -1)
front = rear = 0;
else
rear++;
queue[rear] = num;
}
int delete_element()
{
int val;
if(front == -1 || front>rear)
{
printf(“\n UNDERFLOW”);
return -1;
}
else
{
val = queue[front];
front++;
if(front > rear)
front = rear = -1;
return val;
}
}
int peek()
{
if(front==-1 || front>rear)
{
printf(“\n QUEUE IS EMPTY”);
return -1;
}
else
{
return queue[front];
}
}
void display()
{
int i;
printf(“\n”);
if(front == -1 || front > rear)
printf(“\n QUEUE IS EMPTY”);
else
{
for(i = front;i <= rear;i++)
printf(“\t %d”, queue[i]);
}
}
Output
- Insert an element
- Delete an element
- Peek
- Display the queue
- EXIT
Enter your option : 1
Enter the number to be inserted in the queue : 50