Double ended queue:- It is a special type of queue in which user can perform insertion and deletion operation at both ends of queue. Double ended queue is also known as Deque/ Dequeue/ head-tail linked list. Double ended queue is ADT. It means operations performed on double ended queue are pre-defined(fixed).We can use array and linked list representation for double ended queue. Double ended queue is mainly used in job scheduling algorithm like Steal.
यह क्यू का एक विशेष प्रकार है जिसमे यूजर इंसर्शन एवं डिलीशन ऑपरेशन क्यू के दोनों छोर से कर सकता है डबल एंडेड क्यू को डी क्यू / हेड-टेल लिंक्ड लिस्ट के नाम से भी जाना जाता है। डबल एंडेड क्यू एक ADT है, अर्थात इस पर किये जाने वाले आपरेशन पूर्व निर्धारित होते है। हम अरे या लिंक्ड लिस्ट रिप्रजेंटेशन का प्रयोग कर डबल एंडेड क्यू को मेमोरी में संग्रहित कर सकते है। यह मुख्यत: जॉब शेडूलींग अल्गोरिथम में प्रयुक्त किया जाता है जैसे - स्टील ।
Double ended queue is of following two types-
डबल एंडेड क्यू दो प्रकार का होता है-
1. Input restricted dequeue (इनपुट रिस्ट्रिक्टेड डी क्यू)
2. Output restricted dequeue (आउटपुट रिस्ट्रिक्टेड डी क्यू)
1. Input restricted double ended queue:- a double ended queue in which deletion operation will performed on both ends of queue but insertion operation will performed at only one end (rear1) of queue is called input restricted double ended queue.
एक डबल एंडेड क्यू जिसमे डिलीशन ऑपरेशन क्यू के दोनों छोर से किया जा सकता है परन्तु इंसर्शन ऑपरेशन केवल एक छोर(rear1) से किया जा सकता है, इनपुट रिस्ट्रिक्टेड डी क्यू कहलाता है।
2. Output restricted double ended queue:- a double ended queue in which insertion operation will performed at both ends of queue, but deletion operation will performed at only one end (front1) of queue is called output restricted double ended queue.
एक डबल एंडेड क्यू जिसमे इंसर्शन ऑपरेशन क्यू के दोनों छोर से किया जा सकता है परन्तु डिलीशन ऑपरेशन केवल एक छोर(front1) से किया जा सकता है, आउटपुट रिस्ट्रिक्टेड डी क्यू कहलाता है।
Operations performed on Dequeue are as follows:-
डी क्यू पर किये जाने वाले ऑपरेशन निम्न है:-
1. Insert element at back(rear)
2. Insert element at front
3. Remove last element
4. Remove first element
5. Examine last element
6. Examine first element
C Program to implement Dequeue:-
#include<stdio.h>
#include<conio.h>
#define N 100
int queue[N];
int rear =0, front =0;
void display();
void insertEnd(int);
void insertStart(int);
void insert(int);
int delStart();
int delEnd();
int main()
{
char ch , a='y';
int choice, c, item;
printf("Enter your choice for which deque operation you want to perform operation \n");
do
{
printf("\n1.Input-restricted deque \n");
printf("2.output-restricted deque \n");
printf("\nEnter your choice for the operation : ");
scanf("%d",&c);
switch(c)
{
case 1:
printf("\nDo operation in Input-Restricted c deque\n");
printf("1.Insert");
printf("\n2.Delete from end");
printf("\n3.Delete from begning");
printf("\n4.show or display");
do
{
printf("\nEnter your choice for the operation in c deque: ");
scanf("%d",&choice);
switch(choice)
{
case 1: insertEnd(item);
display();
break;
case 2: item=delEnd();
printf("\nThe item deleted is %d",item);
display();
break;
case 3: item=delStart();
printf("\nThe item deleted is %d",item);
display();
break;
case 4: display();
break;
default:printf("Wrong choice");
break;
}
printf("\nDo you want to continue(y/n) to do operation in input-restricted c deque: ");
ch=getch();
}
while(ch=='y'||ch=='Y');
getch();
break;
case 2 :
printf("\nDo operation in Output-Restricted c deque\n");
printf("1.Insert at the End");
printf("\n2.Insert at the begning");
printf("\n3.Delete the element");
printf("\n4.show or display");
do
{
printf("\nEnter your choice for the operation: ");
scanf("%d",&choice);
switch(choice)
{
case 1: insertEnd(item);
display();
break;
case 2: insertStart(item);
display();
break;
case 3: item=delStart();
printf("\nThe item deleted is %d",item);
display();
break;
case 4: display();
break;
default:printf("Wrong choice");
break;
}
printf("\nDo you want to continue(y/n):");
ch=getch();
}
while(ch=='y'||ch=='Y');
getch();
break ;
}
printf("\nDo you want to continue(y/n):");
ch=getch();
}
while(ch=='y'||ch=='Y');
getch();
}
void display()
{
int i;
printf("\nThe queue elements are:");
for(i=rear;i<front;i++)
{
printf("%d ",queue[i]);
}
}
void insertEnd(int item)
{
char a;
if(front==N/2)
{
printf("\nQueue full\nyou cant enter more elements at the end of c queue");
return;
}
do
{
printf("\nEnter the item to be inserted:");
scanf("%d",&item);
queue[front]=item;
front=front+1;
printf("do you want to continue insertion Y/N");
a=getch();
}
while(a=='y');
}
void insertStart(int item)
{
char a;
if(front==N/2)
{
printf("\nQueue full\nyou cant enter more elements at the start of queue");
return;
}
do
{
printf("\nEnter the item to be inserted:");
scanf("%d",&item);
rear=rear-1;
queue[rear]=item;
printf("do you want to continue insertion Y/N");
a=getch();
}
while(a=='y');
}
int delEnd()
{
int t;
if(front==rear)
{
printf("\nQueue empty");
return 0;
}
front=front-1;
t=queue[front+1];
return t;
}
int delStart()
{
int t;
if(front==rear)
{
printf("\nQueue empty");
return 0;
}
rear=rear+1;
t=queue[rear-1];
return t;
}
No comments:
Post a Comment