Linked Representation of Queue
Insertion into a Queue
LINK_Q_INSERT (INFO, LINK, FRONT, REAR, AVAIL, ITEM)
1.[Available space?] If AVAIL = NULL, then:
Write “OVERFLOW” and Exit.
2.Set NEW = AVAIL, and AVAIL = LINK [AVAIL].
3.Set INFO [NEW] = ITEM and LINK [NEW] = NULL.
4.If FRONT = NULL, then: FRONT = REAR = NEW.
Else: Set LINK [REAR] = NEW and REAR = NEW
Deletion in a Queue
LINK_Q_DELETE (INFO, LINK, FRONT, REAR, AVAIL,
ITEM)
1.[Queue Empty?] If FRONT = NULL, then:
Write “UNDERFLOW” and Exit.
2.Set TEMP = FRONT.
3.Set ITEM = INFO [TEMP].
4.If FRONT = REAR then
5. Set FRONT = REAR = NULL
6.Else
7. Set FRONT = LINK [FRONT]
8.Set LINK [TEMP] = AVAIL and AVAIL = TEMP.
9.Exit
Deques
ØDeque (Double-ended queue) is a linear list in
which elements can be added or removed at either
end but not in the middle.
Ø Two variations of Deque are:
1. Input-restricted deque.
2. Output-restricted deque
Variations of Deque
Input-Restricted Deque:
allows insertion only at one end while deletion in both ends of the list.
Output-Restricted Deque:
allows deletion only at one end while insertion at both the ends of the list.
code to implement queue using link list
#include<iostream>
using namespace std;
struct node{
int info;
node *link;
}*front=NULL,*rear=NULL;
int emptyQueue()
{
if(front==NULL)
{
return 1;
}
else
{
return 0;
}
}
int size()
{
int count=0;
node *ptr=front;
while(ptr!=NULL)
{
++count;
ptr=ptr->link;
}
return count;
}
void Display()
{
node *ptr=front;
while(ptr!=NULL)
{
cout<<endl<<ptr->info<<"\n";
ptr=ptr->link;
}
}
void insert(int item)
{
node *ptr=new node;
ptr->info=item;
ptr->link=NULL;
if(front==NULL)
{
front=rear=ptr;
}
else
{
rear->link=ptr;
rear=ptr;
}
rear->info=item;
}
int delete1()
{
int item=front->info;
if(!emptyQueue())
{
front=front->link;
return item;
}
else
{
return 0;
}
}
int main()
{
int n,item;
while(1)
{
cout<<"\n1. For Insert\n2. Delete\n3. Total Elements\n4. Display\n5. Exit";
cout<<"\nEnter Your Choice ";
cin>>n;
switch(n)
{
case 1:
cout<<"\nEnter the value to be entered";
cin>>item;
insert(item);
break;
case 2:
item=delete1();
if(item!=0)
{
cout<<"\ndeleted item is "<<item;
}
else
{
cout<<"\nQueue is Empty";
}
break;
case 3:
item=size();
if(item!=0)
{
cout<<"Total Elements is queue is "<<item;
}
else
{
cout<<"Queue is empty";
}
break;
case 4:
Display();
break;
case 5:
exit(0);
}
}
return 0;
}
0 Comments