Input Restricted Double Ended Queue ( DEQUE ) :
It is also called as double ended queue, in which insertion and deletion operations are performed from both the ends i.e we can insert an element from rear end or from the front end , we can delete an element from rear end or from the front end. Hence it is commonly referred to as DEQUE,there are two types of Deque.
1.Input Restricted Deque
2.Output Restricted Deque
The following are the operation performed in Input Restricted Deque
1.Insert at rear
2.Delete from front
3.Delete from rear
The following are the operation performed in Output Restricted Deque
1.Insert at rear
2.Insert at front
3.Delete from front
/* Input restricted dequeue using array*/
import java.util.Scanner;
class rkdqinput
{
static int[] a;
static int i,n,item,front=-1,rear=-1,ch;
static Scanner dqi=new Scanner(System.in);
public static void main(String[] args)
{
System.out.printf("\nEnter the length of the input restricted dequeue :\n");
n=dqi.nextInt();
a=new int[n];
while(true)
{
System.out.printf("\n MENU \n\n");
System.out.printf(" 1.Insert at rear\n");
System.out.printf(" 2.Delete from front\n");
System.out.printf(" 3.Delete from rear\n");
System.out.printf(" 4.Display\n");
System.out.printf(" 5.Quit\n");
System.out.printf("Enter ur choice: ");
ch=dqi.nextInt();
switch(ch)
{
case 1:insert_rear();break;
case 2:del_front();break;
case 3:del_rear();break;
case 4:display();break;
case 5:System.exit(1);break;
default:
System.out.printf("u have entered wrong choice");break;
}
System.out.printf("\n");
}
}
static int insert_rear()
{
if((front == 0 && rear == n-1) || (rear==n-1))
{
System.out.printf("\n Dequeue Overflow\n");
return rear;
}
if(front == -1) /* if queue is initially empty */
{
front = 0;
}
rear = rear+1;
System.out.printf("Input the element for adding in dequeue : ");
item=dqi.nextInt();
a[rear]=item;
return rear;
}/*End of insert_rear()*/
static int del_front()
{
if (front == -1)
{
System.out.printf("Dequeue Underflow\n");
return front;
}
System.out.printf("Element deleted from dequeue is : %d\n",a[front]);
a[front]='\0';
if(front == rear) /*Queue has only one element */
{
front = -1;
rear = -1;
}
else
front = front+1;
return front;
}/*End of del_front()*/
static int del_rear()
{
if (front == -1)
{
System.out.printf("Dequeue Underflow\n");
return front;
}
System.out.printf("Element deleted from dequeue is : %d\n",a[rear]);
a[rear]='\0';
if(front == rear) /*queue has only one element*/
{
front = -1;
rear = -1;
}
else
rear=rear-1;
return front;
}/*End of del_rear() */
static void display()
{
if(front==-1 && rear==-1)
{
System.out.printf("\n dequeue is empty \n");
return;
}
else
{
System.out.printf("\n dequeue elements are:");
for(i=0;i<n;i++)
{
if(a[i]=='\0')
System.out.printf("\t");
else
System.out.printf("%d\t",a[i]);
}
}
System.out.printf("\n front = %d rear = %d \n",front,rear);
return;
}
}
It is also called as double ended queue, in which insertion and deletion operations are performed from both the ends i.e we can insert an element from rear end or from the front end , we can delete an element from rear end or from the front end. Hence it is commonly referred to as DEQUE,there are two types of Deque.
1.Input Restricted Deque
2.Output Restricted Deque
The following are the operation performed in Input Restricted Deque
1.Insert at rear
2.Delete from front
3.Delete from rear
The following are the operation performed in Output Restricted Deque
1.Insert at rear
2.Insert at front
3.Delete from front
/* Input restricted dequeue using array*/
import java.util.Scanner;
class rkdqinput
{
static int[] a;
static int i,n,item,front=-1,rear=-1,ch;
static Scanner dqi=new Scanner(System.in);
public static void main(String[] args)
{
System.out.printf("\nEnter the length of the input restricted dequeue :\n");
n=dqi.nextInt();
a=new int[n];
while(true)
{
System.out.printf("\n MENU \n\n");
System.out.printf(" 1.Insert at rear\n");
System.out.printf(" 2.Delete from front\n");
System.out.printf(" 3.Delete from rear\n");
System.out.printf(" 4.Display\n");
System.out.printf(" 5.Quit\n");
System.out.printf("Enter ur choice: ");
ch=dqi.nextInt();
switch(ch)
{
case 1:insert_rear();break;
case 2:del_front();break;
case 3:del_rear();break;
case 4:display();break;
case 5:System.exit(1);break;
default:
System.out.printf("u have entered wrong choice");break;
}
System.out.printf("\n");
}
}
static int insert_rear()
{
if((front == 0 && rear == n-1) || (rear==n-1))
{
System.out.printf("\n Dequeue Overflow\n");
return rear;
}
if(front == -1) /* if queue is initially empty */
{
front = 0;
}
rear = rear+1;
System.out.printf("Input the element for adding in dequeue : ");
item=dqi.nextInt();
a[rear]=item;
return rear;
}/*End of insert_rear()*/
static int del_front()
{
if (front == -1)
{
System.out.printf("Dequeue Underflow\n");
return front;
}
System.out.printf("Element deleted from dequeue is : %d\n",a[front]);
a[front]='\0';
if(front == rear) /*Queue has only one element */
{
front = -1;
rear = -1;
}
else
front = front+1;
return front;
}/*End of del_front()*/
static int del_rear()
{
if (front == -1)
{
System.out.printf("Dequeue Underflow\n");
return front;
}
System.out.printf("Element deleted from dequeue is : %d\n",a[rear]);
a[rear]='\0';
if(front == rear) /*queue has only one element*/
{
front = -1;
rear = -1;
}
else
rear=rear-1;
return front;
}/*End of del_rear() */
static void display()
{
if(front==-1 && rear==-1)
{
System.out.printf("\n dequeue is empty \n");
return;
}
else
{
System.out.printf("\n dequeue elements are:");
for(i=0;i<n;i++)
{
if(a[i]=='\0')
System.out.printf("\t");
else
System.out.printf("%d\t",a[i]);
}
}
System.out.printf("\n front = %d rear = %d \n",front,rear);
return;
}
}
No comments:
Post a Comment