Linear Queues - Introduction and Implementation


A queue is a data structure and generally called as linear queue ADT (abstract data type). Linear queues can be implemented using arrays or linked lists. Read this article for a brief introduction of queues and the C programs to implement linear queues using arrays and linked lists.

Introduction to Linear Queues

A Queue is a data structure which follows FIFO (first in first out) principle. The element which is entered first into the queue (first in) is the element which can be first deleted from the queue (first out). Two operations ENQUEUE and DEQUEUE are commonly used for queues. Here, ENQUEUE means insertion and DEQUEUE means deletion. Operations like insertion, deletion can be performed at both ends of a queue. Two pointers called FRONT and REAR are used for queues. Here, FRONT represents the end at which deletion can be performed and REAR represents the end at which insertion can be performed. There are some other operations for queues which are PEEK, ISFULL and ISEMPTY. Here, PEEK is used to get the first element of the queue without removing it and ISFULL, ISEMPTY are used to check whether the queue is full (over flow error) or empty (under flow error) respectively. Let us take some real life examples. We stand in a line while boarding a bus and while getting a movie ticket etc,. In the both cases, who gets first into the line (queue) gets out first from the line (queue) i.e. FIFO principle. The image below shows a linear queue, it operations (only insertion and deletion but not others) and pointers.

Linear Queue

Implementation of Linear Queues

Linear Queues can be implemented using arrays or linked lists.

C Program to implement Linear Queues using Arrays

Program
#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
#define SIZE 5
int queue[SIZE];
int front=-1;
int rear=-1;
int underflow()
{
if((front==-1)&&(rear==-1))
{
printf("\n Linear Queue is Empty \n");
return(0);
}
else
{
return(1);
}
}
int overflow()
{
if(rear==SIZE-1)
{
printf("\n Linear Queue is Full \n");
return(1);
}
else
{
return(0);
}
}
void enqueue(int item)
{
if((front==-1)&&(rear==-1))
{
front=0;
rear=0;
}
else
{
rear=rear+1;
}
queue[rear]=item;
}
void dequeue()
{
if(front==rear)
{
front=-1;
rear=-1;
}
else
{
front=front+1;
}
}
void display()
{
int i;
for(i=front;i<=rear;i++)
{
printf("%d ",queue[i]);
}
}
void menu()
{
int choice,item;
printf("\n\n Linear Queue Operations");
printf("\n 1.Insert");
printf("\n 2.Delete");
printf("\n 3.Display");
printf("\n 4.Exit");
printf("\n Enter your choice : ");
scanf("%d",&choice);
switch(choice)
{
case 1:
if(overflow()==0)
{
printf("\n Enter the item to be inserted : ");
scanf("%d",&item);
enqueue(item);
}
getch();
menu();
break;
case 2:
if(underflow()==1)
dequeue();
getch();
menu();
break;
case 3:
if(underflow()==1)
{
printf("\n Linear Queue is : ");
display();
}
getch();
menu();
break;
case 4:
exit(0);
break;
default:
printf("\n Your choice is invalid \n");
menu();
break;
}
}
void main()
{
clrscr();
menu();
}

Output
Linear Queue Operations
1.Insert
2.Delete
3.Display
4.Exit
Enter your choice : 1
Enter the item to be inserted : 9

Linear Queue Operations
1.Insert
2.Delete
3.Display
4.Exit
Enter your choice : 1
Enter the item to be inserted : 7

Linear Queue Operations
1.Insert
2.Delete
3.Display
4.Exit
Enter your choice : 3
Linear Queue is : 9 7

Linear Queue Operations
1.Insert
2.Delete
3.Display
4.Exit
Enter your choice : 1
Enter the item to be inserted : 5

Linear Queue Operations
1.Insert
2.Delete
3.Display
4.Exit
Enter your choice : 1
Enter the item to be inserted : 3

Linear Queue Operations
1.Insert
2.Delete
3.Display
4.Exit
Enter your choice : 1
Enter the item to be inserted : 1

Linear Queue Operations
1.Insert
2.Delete
3.Display
4.Exit
Enter your choice : 1
Linear Queue is Full

Linear Queue Operations
1.Insert
2.Delete
3.Display
4.Exit
Enter your choice : 3
Linear Queue is : 9 7 5 3 1

Linear Queue Operations
1.Insert
2.Delete
3.Display
4.Exit
Enter your choice : 2

Linear Queue Operations
1.Insert
2.Delete
3.Display
4.Exit
Enter your choice : 2

Linear Queue Operations
1.Insert
2.Delete
3.Display
4.Exit
Enter your choice : 2

Linear Queue Operations
1.Insert
2.Delete
3.Display
4.Exit
Enter your choice : 3
Linear Queue is : 3 1

Linear Queue Operations
1.Insert
2.Delete
3.Display
4.Exit
Enter your choice : 2

Linear Queue Operations
1.Insert
2.Delete
3.Display
4.Exit
Enter your choice : 2

Linear Queue Operations
1.Insert
2.Delete
3.Display
4.Exit
Enter your choice : 3
Linear Queue is Empty

Linear Queue Operations
1.Insert
2.Delete
3.Display
4.Exit
Enter your choice : 5
Your choice is invalid

Linear Queue Operations
1.Insert
2.Delete
3.Display
4.Exit
Enter your choice : 4

C Program to implement Linear Queues using Linked Lists


Program
#include<stdio.h>
#include<conio.h>
#include<malloc.h>
#include<stdlib.h>
struct queue
{
int data;
struct queue *next;
}*front,*rear,*newnode,*ptr;
int underflow()
{
if((front==NULL)&&(rear==NULL))
{
printf("\n Linear Queue is Empty \n");
return(0);
}
else
{
return(1);
}
}
void enqueue(int item)
{
newnode=(struct queue*)malloc(sizeof(struct queue));
newnode->data=item;
if((front==NULL)&&(rear==NULL))
{
front=newnode;
rear=newnode;
newnode->next=NULL;
}
else
{
rear->next=newnode;
newnode->next=NULL;
rear=newnode;
}
}
void dequeue()
{
if(front==rear)
{
front=NULL;
rear=NULL;
}
else
{
front=front->next;
}
}
void display()
{
int i;
ptr=front;
i=1;
while(ptr!=NULL)
{
printf("%d ",ptr->data);
ptr=ptr->next;
i++;
}
}
void menu()
{
int choice,item;
printf("\n\n Linear Queue Operations");
printf("\n 1.Insert");
printf("\n 2.Delete");
printf("\n 3.Display");
printf("\n 4.Exit");
printf("\n Enter your choice : ");
scanf("%d",&choice);
switch(choice)
{
case 1:
printf("\n Enter the item to be inserted : ");
scanf("%d",&item);
enqueue(item);
getch();
menu();
break;
case 2:
if(underflow()==1)
{
dequeue();
}
getch();
menu();
break;
case 3:
if(underflow()==1)
{
printf("\n Linear Queue is : ");
display();
}
getch();
menu();
break;
case 4:
exit(1);
break;
default:
printf(" Your choice is invalid \n\n");
menu();
break;
}
}
void main()
{
clrscr();
menu();
}

Output
Linear Queue Operations
1.Insert
2.Delete
3.Display
4.Exit
Enter your choice : 1
Enter the item to be inserted : 20

Linear Queue Operations
1.Insert
2.Delete
3.Display
4.Exit
Enter your choice : 1
Enter the item to be inserted : 40

Linear Queue Operations
1.Insert
2.Delete
3.Display
4.Exit
Enter your choice : 1
Enter the item to be inserted : 60

Linear Queue Operations
1.Insert
2.Delete
3.Display
4.Exit
Enter your choice : 1
Enter the item to be inserted : 80

Linear Queue Operations
1.Insert
2.Delete
3.Display
4.Exit
Enter your choice : 3
Linear Queue is : 20 40 60 80

Linear Queue Operations
1.Insert
2.Delete
3.Display
4.Exit
Enter your choice : 2

Linear Queue Operations
1.Insert
2.Delete
3.Display
4.Exit
Enter your choice : 2

Linear Queue Operations
1.Insert
2.Delete
3.Display
4.Exit
Enter your choice : 2

Linear Queue Operations
1.Insert
2.Delete
3.Display
4.Exit
Enter your choice : 3
Linear Queue is : 80

Linear Queue Operations
1.Insert
2.Delete
3.Display
4.Exit
Enter your choice : 2

Linear Queue Operations
1.Insert
2.Delete
3.Display
4.Exit
Enter your choice : 2
Linear Queue is Empty

Linear Queue Operations
1.Insert
2.Delete
3.Display
4.Exit
Enter your choice : 5
Your choice is invalid

Linear Queue Operations
1.Insert
2.Delete
3.Display
4.Exit
Enter your choice : 4


Comments

No responses found. Be the first to comment...


  • Do not include your name, "with regards" etc in the comment. Write detailed comment, relevant to the topic.
  • No HTML formatting and links to other web sites are allowed.
  • This is a strictly moderated site. Absolutely no spam allowed.
  • Name:
    Email: