Resources » Articles/Knowledge Sharing » Education

C ++ program to implement linear queue, circular queue and dequeue


Posted Date: 18-Aug-2013  Last Updated:   Category: Education    
Author: Member Level: Gold    Points: 20


Are you looking for C ++ programs? Here are few C ++ programs which implements linear queue using linked lists, circular queue, dequeue using double linked lists. Read this complete article and learn these three programs easily.



Circular Queue


Below C ++ programming code implements circular queue using templates. The advantage of templates is that we can use any data type for arrays by simply chaning it in main function. Operations performed on circular queue are insertion, deletion, and traversing. Circular queues also follows FIFP concept.

# include < iostream.h >
# include < conio.h >

template< class T >

class Queue
{
T * arr;
int front, rear;
int size;

public:
Queue(int s=10);
void Enqueue(T &n);
T Dequeue();
int IsEmpty();
int IsFull();
};

template< class T >
Queue< T > :: Queue(int s=10)
{
size=s;
arr=new T[size];
front=rear=-1;
}

template< class T >
void Queue< T > :: Enqueue (T &n)
{
if(IsFull())
{
cout< < "Queue is full";
getch();
return;
}
rear++;
rear= rear size;
arr[rear]=n;if(front==-1)
front=0;
}

template< class T >
T Queue< T > :: Dequeue()
{
if (IsEmpty())
{
cout< < endl< < " Queue is empty";
return -1;
}
T temp=arr[front];
if(front==rear)
front=rear= -1;
else
front= front size;
return temp;
}

template< class T >
int Queue< T > :: IsFull()
{
int r=(rear+1)%size;
if(r==front)
return 1;
else
return 0;
}

void main()
{
int ch,n;
Queue< int > q(5);
do
{
clrscr();
cout < < endl< < "1 Add";
cout < < endl< < "2 Remove";
cout < < endl< < "3 Exit";
cout < < endl< < "enter your choice";
cin>>ch;
if(ch==1)
{
cout < < endl< < "enter a number";
cin>>n;
q.Enqueue(n);
}
else if(ch==2)
{
n=q.Dequeue();
cout < < endl< < "Removed element is:";
getch();
}
}
while(ch!=3);
}


Linear Queue


Queues is linear data structure which works on the concept of 'first in-first out [FIFO]' i.e., the element which is entered first into the list is retrived first from the queue.

# include< iostream.h >
# include< conio.h >
# include< stdio.h >

class node
{
public:
class node*next;
int data;
};

class queue : public node
{
node *head;
int front, rear;
public:
queue()
{
front= -1;
rear= -1;
}
void push(int x)
{
if(rear< 0)
{
head= new node;
head-> next= NULL;
head-> data=x;
rear++;
}
else
{
node *temp, *temp1;
temp=head;
if(rear>=4)
{
cout < < endl< < "queu is overflow";
return;
}
rear ++;
while( temp->next!= NULL)
temp=temp->next;
temp1=new node;
temp-> next= temp1;
temp1-> next= NULL;
temp1->data=x;
}
}

void display()
{
node *temp;
temp= head;
if(rear< 0)
{
cout < < endl< < "queue is under flow";
return;
}
while( temp!=NULL)
{
cout < < endl< < temp->data< < "";
temp=temp-> next;
}
}

void pop()
{
node *temp;
temp= head;
if(rear< 0)
{
cout < < endl< < "queue underflow";
return;
}
front++;
head=head->next;
}
};

void main()
{
queue s1;
int ch;
while(1)
{
cout < < endl< < "1 push \n 2 pop \n 3 display \n 4 exit";
cout < < endl< < "enter your choice";
cin>>ch;
switch(ch)
{
case 1: cout < < endl< < "enter an element";
cin>>ch;
s1.push(ch);
break;
case 2: s1.pop();
brak;
case 3: s1.display();
brea;
case 4: exit(0);
}
}
return(0);
getch();
}


Dequeue [Double ended Queue]


Double ended Queues, shortly termed as Dequeue are used to add or delee elemens at both the ends of the queue i.e., at front and rear ends of the queue. Below is a C++ program code which implements Double ended queue [Dequeue] using double linked lists. Generally dequeue's are reffered as head-tail lists.

# include< iostream.h >
# include< conio.h >
# include< stdio.h >

class dequeue
{
public:
int data;
dequeue *next, *prev, *first, *last;
void insert_at_fisrt();
void insert_at_last();
void delete_at_first();
void delete_at_last();
void display();
};

void main()
{
dequeue de;
int ch;
clrscr();
dequeue *tempp;
while(1)
{
cout< < " Insert at first \n";
cout< < " Insert at last \n";
cout< < " Delete at first \n";
cout< < " Delete at last \n";
cout< < " Display the list \n";
cin>>ch;
switch(ch)
{
case 1: de.insert_at_fisrt();
break;
case 2: de.insert_at_last()
break;
case 3: de.delete_at_fisrt()
break;
case 4: de.delete_at_last()
break;
case 5: de.display();
break;
default: cout < < "\n invalid entry";
}
}
}

void dequeue :: delete_at_first()
{
if(first->next== NULL)
first=last=NULL;
else
{
first= first-> next;
first-> prev= NULL;
}
display();
return;
}

oid dequeue :: insert_at_last()
{
dequeue *temp;
cout< < "\n enter an element";
cin>>temp-> data;
temp= temp-> next;
temp> next= NULL;
temp-> prev= NULL;
if(first== NULL && last== NULL)
first= last= temp;
else
{
last-> next= temp;
temp-> prev= last;
last= temp;
}
display();
return;
}

void dequeue :: inser_at_first()
{
dequeue *temp;
cout< < "enter an element";
cin>> temp-> data;
temp= temp-> next;
temp-> next= NULL;
temp-> prev= NULL;
if(first== NULL && last== NULL)
first= last= temp;
else
{
first-> prev= temp;
temp-> next= first;
first= temp;
first-> prev= Null;
}
display();
return;
}

void dequeue :: display();
{
dequeue *p;
p= first;
if(irst== NULL && last && = NULL)
cout< < "list is empty";
else
{
cout< < "\n";
while(p!=NULL)
{
cout< < p-> data< < "";
p= p-> next;
}
}
return;
}


Did you like this resource? Share it with your friends and show your love!




Responses to "C ++ program to implement linear queue, circular queue and dequeue"
Author: Mohd waseem    21 Aug 2013Member Level: Silver   Points : 2
Well this is a good thing that you have mentioned C++ programs in this article. But I have little confusion about templates that you have mentioned. I would be very thankful to you if you write an article on stacks using linked lists.


Author: vamshi    21 Aug 2013Member Level: Gold   Points : 0
@ Waseem

Yes, I agree that templates causes little confusion while reading the program. Within few days I will post this stacks using linked lists program.



Feedbacks      

Post 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:   Sign In to fill automatically.
    Email: (Will not be published, but required to validate comment)



    Type the numbers and letters shown on the left.


    Submit Article     Return to Article Index

    Awards & Gifts
    Active Members
    TodayLast 7 Daysmore...

    Online Members

    uma shankar
    More...
    ISC Technologies, Kochi - India. Copyright © All Rights Reserved.