♠ Posted by Unknown in C'Language,Data Structure at 10:55
Double Ended Queue with Operations
We know that in a stack insertion
and deletion are possible only at one end (LIFO). While in a queue insertion at
one end and deletion at other end. That is operations in queue is performed in
(FIFO) basis. Double ended queue is a linear list in which insertions and
deletions are possible at either end.
Thus we can say that dqueue is more superior representations of linear
list as compared to stack and simple queue. Other than the dqueue, there are
other two forms of dqueue. Double ended queue is also known as dqueue.
Following figure shows a dqueue.
1. Input restricted
dqueue (Insertion at one end)
2. Output restricted
dqueue (Deletion at one end)
ALGORITHM OF DOUBLE-ENDED QUEUE.
1. Insertion in Double-Ended Queue.
Step 1: [Check overflow condition]
If rear >= n
and front = 0
Output “overflow”
and return
Step 2: [Check front pointer value]
If front > 0
front = front – 1
else
return
Step 3: [Insert element at the front end]
Q [front] = value
Step 4: [Check rear pointer value]
If rear < n
rear = rear + 1
else
return
Step 5: [Insert element at the rear end]
Q [rear] = value
Step 6: return
2. Deletion in Double-Ended queue.
Step 1: [Check for underflow]
If front = 0 and
rear = 0
Output “Underflow”
and return
Step 2: [Delete element at front end]
If front > 0
Value = Q [front]
Return (value)
Step 3: [Check queue for empty]
If front = rear
front = rear = 0
else
front = front + 1
Step 4: [Delete element at the rear end]
If rear > 0
Value = Q [rear]
Return (value)
Step 5: [Check queue for empty]
If front = rear
front = rear = 0
else
rear = rear – 1
Step 6: return
Example:
/*USE OF
DOUBLE-ENDED QUEUE USING ARRAY.*/
#include<stdio.h>
#define
SIZE 3
int
arr[SIZE];
int
front=0;
int
rear = 0;
main()
{
int ans;
clrscr();
do
{
printf("1.Enter New Element From Right
:\n");
printf("2.Remove Element From Right
:\n");
printf("3.Enter New Element From Left
:\n");
printf("4.Remove Element From Left
:\n");
printf("5.Exit :\n");
printf("Enter Your Choice :");
scanf("%d",&ans);
switch(ans)
{
case 1:
r_insert();
break;
case 2:
r_remove();
break;
case 3:
l_insert();
break;
case 4:
l_remove();
break;
case 5:
break;
default:
printf("You have
entered wronge choice....");
}
}while(ans!=5);
getch();
return;
}
r_insert()
{
int newitem;
if(rear >= SIZE)
{
printf("Your QUEUE is full from RIGHT
side....");
getch();
return;
}
else
{
printf("Enter the New item :");
scanf("%d",&newitem);
arr[++rear]=newitem;
}
if(front <= 0)
{
front = 1;
}
getch();
return;
}
r_remove()
{
int remitem;
if(rear <= 0)
{
rear = 0;
front = 0;
printf("Your QUEUE is EMPTY from RIGTH
side...\n");
getch();
return;
}
else
{
remitem = arr[rear--];
printf("The removed item is :
%d\n",remitem);
}
getch();
return;
}
l_remove()
{
int remitem;
if(front <= 0 )
{
printf("Your QUEUE is EMPTY from LEFT
side...\n");
getch();
return;
}
else
{
remitem = arr[front++];
printf("The removed item is :
%d\n",remitem);
}
if(front > rear)
{
front = 0;
}
getch(); return;}
l_insert()
{
int newitem;
if(front <= 1)
{
front = 0;
rear = 0;
printf("Your QUEUE is FULL from the LEFT
side...\n");
getch();
return;
}
else
{
printf("Enter the New element :");
scanf("%d",&newitem);
arr[--front]=newitem;
}
getch();
return;
}
0 comments:
Post a Comment