Here you will learn about linear queue in C++.
What is Queue?
The queue is a linear data structure where operations of insertion and deletion are performed at separate ends that are known as front and rear. The queue follows FIFO (First in First Out) concept. First element added to the queue will be first one to be removed.
In this program we will implement linear queue using linked list. It is a menu driven program that contains four options insert, delete, display and exit. The program will ask the user to enter the choice and then appropriate functions are invoked to perform specific operation according to the user’s choice.
Also Read: Circular Queue in C
Program for Linear Queue in C++
#include<iostream>
#include<stdlib.h>
using namespace std;
struct node
{
int data;
struct node *next;
}*front=NULL,*rear,*temp;
void ins()
{
temp=new node;
cout<<"Enter data:";
cin>>temp->data;
temp->next=NULL;
if(front==NULL)
front=rear=temp;
else
{
rear->next=temp;
rear=temp;
}
}
void del()
{
if(front==NULL)
cout<<"Queue is empty\n";
else
{
temp=front;
front=front->next;
cout<<"Deleted node is "<<temp->data<<"\n";
delete(temp);
}
}
void dis()
{
if(front==NULL)
cout<<"Queue is empty\n";
else
{
temp=front;
while(temp!=NULL)
{
cout<<temp->data<<"->";
temp=temp->next;
}
}
}
int main()
{
int ch;
while(1)
{
cout<<"\n\n*** Menu ***"<<"\n1.Insert\n2.Delete\n3.Display\n4.Exit";
cout<<"\n\nEnter your choice(1-4):";
cin>>ch;
cout<<"\n";
switch(ch)
{
case 1: ins();
break;
case 2: del();
break;
case 3: dis();
break;
case 4: exit(0);
break;
default: cout<<"Wrong Choice!!!";
}
}
return 0;
}
Output
*** Menu ***
1.Insert
2.Delete
3.Display
4.Exit
1.Insert
2.Delete
3.Display
4.Exit
Enter your choice(1-4):1
Enter data:8
*** Menu ***
1.Insert
2.Delete
3.Display
4.Exit
1.Insert
2.Delete
3.Display
4.Exit
Enter your choice(1-4):1
Enter data:12
*** Menu ***
1.Insert
2.Delete
3.Display
4.Exit
1.Insert
2.Delete
3.Display
4.Exit
Enter your choice(1-4):3
8->12->
*** Menu ***
1.Insert
2.Delete
3.Display
4.Exit
Enter your choice(1-4):4
Insertion
In the insertion operation, temp points to the new node. If this is first node to be inserted then front will be NULL and now both front and rear points to this new node. If front is not NULL then insertion is similar to adding the node at the end of linked list. The next pointer of rear points to temp and rear becomes temp.
Deletion
For deletion purpose, it is first checked whether front is NULL, if it is NULL, we display the message “Queue is empty”. In case the queue is not empty, deletion is done in such a way that temp pointer points to front and front pointer points to its next node. After displaying data for the node to be deleted, node is deleted by delete(temp) function.
Display
For display, it is first checked whether front is NULL, if it is NULL, we display the message “Queue is empty”. If queue is not empty, front pointer is assigned to temp and data for all the nodes are displayed till temp does not become NULL.
If you have any doubts related to above linear queue in C++ program then you can ask it by commenting below.
nice and easy to understand!
Seems nice to here that my articles are easy to understand. Thanks Rakhi for visiting.
It saved my board exam! thanks a lot.. 🙂
the code :
while(temp->next!=NULL)
in dis()
is wrong. Because if its the last node it will always point to NULL so when you display your queue the last element that was inserted wont be displayed.
Use
while(temp!=NULL) in its place.
thanks a lot for telling the mistake 🙂
sir….Is dynamic and linked queue are different ?