DEQUE implementation Using Arrays

-

 Deque is a double Ended queue, where you can insert and delete from both front and rear end.

Deque is of two types: 
1) INPUT restricted Deque - in it you can enter the element from only one end either from front or rear. But can delete from both ends.
2) OUTPUT restricted Deque - In it you can delete elements from only one end either from front or rear. But can insert from both ends.
A Deque follows properties of both stack and queue.
It follows STACK (LIFO) in such a way that we can restrict insertion and deletion from only one end, like Stack.
It follows QUEUE (FIFO) Property in such a way that we can restrict insertion from rear end and deletion from front end, and we can set any end as rear or front because elements can be deleted or inserted from both the end.

CODE:

#include<conio.h>
#include<stdlib.h>
#include<stdio.h>
void enqueue_front(int d[], int *f, int *r, int size)
{
    int data;
    if((*f==0 && *r==size-1) ||(*f==*r+1) )
        printf("Deque is Full !"); /*(*f==0 && *r==size-1) this condition arrived only when \n
         `rear was at end and front was at any arbitrary index behind rear.\n
        Than front came back again and again by one position to enter the data,\n
         and finally at index 0. Now rear is at end and all elements \n
          are entered from end towards front, hence Deque become full. Don't use (*r+1)%n==*f to check full or not \n
          You can use it in enqueue_rear*/
    else if(*f==-1 && *r==-1)
    {
        *f=0; *r=0;
        printf("Enter the data: ");
        scanf("%d",&data);
        d[*f]=data;
    }
    else if(*f==0)
    {
        *f=size-1;
        printf("Enter the data: ");
        scanf("%d",&data);
        d[*f]=data;
    } /* Peeche hi toh jaayega front agar front se enter karwaaoge, \n
    kyunki agar front se enter hoga toh entered element pichle wale se bhi pehle aana chahiya*/
    else
    {
        *f=*f-1;
        printf("Enter the data: ");
        scanf("%d",&data);
        d[*f]=data;
    }
}
void enqueue_rear(int d[], int *f, int *r, int size)
{
// Similar to enqueue in circular Queue;
    int data;
if(((*r)+1)%size==*f)
    printf("Deque is Full!");
else if(*f==-1 && *r==-1)
    {
        *f=0;*r=0;
        printf("Enter the data: ");
        scanf("%d",&data);
        d[*r]=data;
    }
else
    {
        *r=(*r+1)%size;
        printf("Enter the data: ");
        scanf("%d",&data);
        d[*r]=data;
    }
}
void dequeue_front(int d[], int *f, int *r, int size)
{ // Similar to dequeue in circular Queue.
    if(*f==-1 && *r==-1)
        printf("Queue is empty\n");
    else if(*f==*r)
    {
        printf("Deleted element is: %d\n\nAnd Queue is now EMPTY\n",d[*f]);
        *r=-1;*f=-1;
    }
    else
    {
        printf("deleted element is %d\n",d[*f]);
        *f=(*f+1)%size;
    }
}
void dequeue_rear(int d[], int *f, int *r, int size)
{/* rear is that from where elements are inserted, \n
     Now bring back rear in order to delete the element from end. */
if (*f==-1 && *r==-1)
    printf("Deque is empty !\n");
else if(*f==*r){
    printf("Deleted element is: %d\n\nAnd Queue is now EMPTY\n",d[*r]);
    *f=-1; *r=-1;}
else if(*r==0)
    {
        printf("Deleted element is: %d\n",d[*r]);
        *r=size-1;
    }
else
    {
        printf("Deleted element is: %d\n",d[*r]);
        *r=*r-1;
    }
}
void display(int d[], int f, int r, int size)
{
    int i;
if(f==-1 && r==-1)
    printf("Deque is empty !\n");
else
{
    i=f;
    printf("Deque is\nFront\n");
    while(i!=r)
    {
        printf("%d\n",d[i]);
        i=(i+1)%size;
    }printf("%d",d[i]);printf("\nEnd\n");
}
}
int main()
{
    int n,ch,choice=1,data, tp1=1,tp2=1,type;
    printf("Enter the size of Queue: ");
    scanf("%d",&n);
    int deque[n];
    int front=-1, rear=-1;
    while(choice==1){
    printf("Enter\n1.For Input restricted Deque\n2.For Output restricted Deque\n");
    scanf("%d",&type);
    if(type==1)
    {
        while(tp1==1)
        {
            printf("Enter 1. to Enqueue from front end\n");
            printf("Enter 2. to Dequeue from front end \n");
            printf("Enter 3. to Dequeue from rear end\n");
            printf("Enter 4. to Display\n");
            printf("Enter choice: ");
            scanf("%d",&ch);
            if(ch==1)
                enqueue_front(deque, &front, &rear, n);
            else if(ch==2)
                dequeue_front(deque, &front, &rear,n);
            else if (ch==3)
                dequeue_rear(deque, &front, &rear,n);
            else if(ch==4)
                display(deque, front, rear, n);
            else
                printf("Invalid choice, ");
            printf("Want to continue(0,1): ");
            scanf("%d",&tp1); if(tp1!=1) choice=0;
            //set choice=0 to get out of outermost loop.
        }
    }
    else if(type==2)
    {
        while(tp2==1)
        {
            printf("Enter 1. to Enqueue from front end.\n");
            printf("Enter 2. to Enqueue from rear end\n");
            printf("Enter 3. to Dequeue from front end\n");
            printf("Enter 4. to Display\n");
            printf("Enter choice: ");
            scanf("%d",&ch);
            if(ch==1)
                enqueue_front(deque, &front, &rear, n);
            else if(ch==2)
                enqueue_rear(deque, &front, &rear, n);
            else if (ch==3)
                dequeue_front(deque, &front, &rear,n);
            else if(ch==4)
                display(deque, front, rear, n);
            else
                 printf("Invalid choice, ");
            printf("Want to continue(0,1): ");
            scanf("%d",&tp2); if(tp2!=1) choice=0;
        }
    }
    else
    {printf("\nSelect a Valid Deque, Want to continue(0,1): ");
    scanf("%d",&choice);}
    }
}

Comments

Post a Comment

Popular posts from this blog

First_Come_First_Serve CPU Scheduling

-
#include<stdio.h> #include<conio.h> struct proc {     int id;     int burst;     int at; }; int main() {     int n,i,j,total_waiting_time,waiting_time;     printf("Enter the number of processess: ");     scanf("%d",&n);     struct proc p[n],temp;     f or(i=0;i<n;i++)     {         p[i].id=i;         printf("Enter the arrival time of the process: ");         scanf("%d",&p[i].at);         printf("Enter the burst time of the process: ");         scanf("%d",&p[i].burst);     }     for(i=0;i<n;i++)     {         for(j=i+1;j<n;j++)         {             if(p[j].at<p[i].at)             {                 ...
Read more

Reversing stack Method 2 !! (One Helper Stack only)

-
#include   <bits/stdc++.h> using   namespace   std ; stack < int >  rev ( stack < int >  s ) {      int   size  =  s . size (),  x ,  y ,  t ;      stack < int >  s2 ;      size  -=  1 ;      while  ( size --)     {          t  =  size  +  1 ;          x  =  s . top ();          s . pop ();          while  ( t --)         {              s2 . push ( s . top ());              s . pop ();         }  ...
Read more

Populating Next Right Pointers in Each Node in O(1) space (without queue and level order)

-
Image
Example 1: Input: root = [1,2,3,4,5,6,7] Output: [1,#,2,3,#,4,5,6,7,#] Explanation: Given the above perfect binary tree (Figure A), your function should populate each next pointer to point to its next right node, just like in Figure B. The serialized output is in level order as connected by the next pointers, with '#' signifying the end of each level. Example 2: Input: root = [] Output: [] class Solution { public:     Node * connect ( Node * root )     {         Node * p1 = root , * p2 ;         while ( p1 != NULL )         {             p2 = p1 ;             while ( p2 != NULL )             {                 if ( p2 -> left )                     p2 -> left -> next = p2 -> right ;       ...
Read more

Calculate factorial of large numbers !! (Using Arrays)

-
#include   <bits/stdc++.h> using   namespace   std ; #define   max   10000 int   main () {      int   n ,  c ,  j ,  k ,  x ,  i ;      int   a [ max ];      cout   <<   "Enter the number: " ;      cin   >>   n ;      j  =  0 ;  // j will be pointing to new index created to stored carry      a [ 0 ] =  1 ;      for  ( i  =  2 ;  i  <=  n ;  i ++)     {          c  =  0 ;  //carry when each number of array is multiplied by i          //(i is a...
Read more

Multiplication of large numbers (Given in string format)

-
  class   Solution { public:      string   multiply ( string   num1 ,  string   num2 )     {          if  ( num1  ==  "0"  ||  num2  ==  "0" )              return   "0" ;          if  ( num1  ==  "1" )              return   num2 ;          if  ( num2  ==  "1" )              return   num1 ;          if  ( num1 . size () ==  1  &&  num2 . size () ==  1 )         {           ...
Read more

Left View of Binary Tree (Method 1 using recursion)

-
#include   <iostream> #include   <vector> using   namespace   std ; struct   TreeNode {      int   val ;      TreeNode  * left ;      TreeNode  * right ;      TreeNode () :  val ( 0 ),  left ( nullptr ),  right ( nullptr ) {}      TreeNode ( int   x ) :  val ( x ),  left ( nullptr ),  right ( nullptr ) {}      TreeNode ( int   x ,  TreeNode   * left ,  TreeNode   * right ) :                              val ( x ),  left ( left ),  right ( right ) {} }; TreeNode   * BuildTree () {      int   d ;      cin   >>   d ;      if  ( d  == -...
Read more

Check Bracket Sequence

-
#include<bits/stdc++.h> using namespace std; int main() {     int i,f,top=-1,size;     string s;     cin>>s;     size=s.size();     char a[size];     f=1;     for(i=0;i<s.size() && f==1;i++)     {         if(s[i]=='(')         a[++top]='(';         else if(s[i]==')')         {             if(top==-1)             f=0;             else             top-=1;         }     }     if(top!=-1 || f==0)     cout<<"invalid\n";     else     cout<<"Valid"; }
Read more

Image Multiplication

-
https://practice.geeksforgeeks.org/problems/image-multiplication0627/1 Input: 1 / \ 3 2 / \ / \ 7 6 5 4 / \ \ / \ \ 11 10 15 9 8 12 Output: 332 Explanation: Sum = (1*1) + (3*2) + (7*4) + (6*5) + (11*12) + (15*9) = 332 class Solution {     public:     void treeHelper ( Node * a , Node * b , long long int & ans )     {         if (a== NULL ||b== NULL )         return ;         long long int temp=( a -> data * b -> data )%( 1000000007 );         ans=(ans+temp)%( 1000000007 );         treeHelper ( a -> left , b -> right , ans);         treeHelper ( a -> right , b -> left , ans);     }   ...
Read more

Boundary Traversal of binary tree

-
struct Node {     int data;     Node * left, * right; }; class Solution { public:     void call_left ( vector < int > & v , Node * root )     {         if ( root == NULL )             return ;         if ( root ->left == NULL && root ->right == NULL )             return ; // don't push the leaf nodes.         v . push_back ( root ->data);         if ( root ->left)             call_left ( v , root ->left);         else             call_left ( v , root ->right);     }     void call_leaves ( vector < int > & v , Node * root )     {         if ( root == NULL )             return ;   ...
Read more

BST to greater sum tree

-
  // Input: //            2 //          /    \ //         1      6 //               /  \ //              3    7 // Output: 18 16 13 7 0 (InOrder) // Explanation: // Every node is replaced with the sum of nodes greater than itself. // The resultant tree is: //                16 //              /    \ //            18       7 //                   /   \ //                  13    0 //Bhaskar Varshney #include <iostream> #include <queue> using namespace std; struct TreeNode {     int val;     TreeNode *left;     TreeNode *rig...
Read more