Data Structure - [Double Ended Queue Operations]

♠ Posted by Unknown in , 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