Implementing a circular Queue using Linked List

[srinivaskolli]

Hi everyone, I have to implement a circular queue using linked list here.
We imagine a queue in a circular shape where we break at a point such that now it has 2 ends
Now we have to perform insertion and deletion at both ends one at a time
I was able to perform this functionality below
Now i have to assume this queue has a size 5 , and if i insert the 6th element from any end left or right, the element on the other end should get deleted. I am unable to perform this task here efficiently.
Can anyone help me with this
For ex. the queue is 4 5 6 7 8 .....now if i insert 9 on the right end the new queue shud be 5 6 7 8 9
and vice-versa

/*Circular Queue implementation using linked list
Written by Srinivas Kolli
Date- 14-07-2012 */

#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
#include<iostream>

using namespace std;

struct node
       {
        struct node *lptr;
        int info;
        struct node *rptr;
       }
*start=NULL,*last=NULL;

// Insert from Left End
void insert_front()
{
      struct node *n;
      n=(struct node*)malloc(sizeof(struct node));

       if(n==NULL)
       {
        cout<<"\nOverflow\n";
        getch();
       }
       if(n>=5)
        {
         delete_end();    
        }
       else
       {
           cout<<"Item=";
           scanf("%d",&n->info);
           n->lptr=NULL;

                if(start==NULL)
                {
                 start=n;
                 last=n;
                 start->rptr=NULL;
                }
                 else
                {
                 n->rptr=start;
                 start->lptr=n;
                 start=n;
                }
        }


}// End of Insert from Left

//Insert from Right End
void insert_end()
{

     struct node *n;
     n=(struct node*)malloc(sizeof(struct node));

     if(n==NULL)
     {
      cout<<"Overflow\n";
      getch();
     }
     else
     {
      cout<<"Item=";
      scanf("%d",&n->info);
      n->rptr=NULL;

          if(start==NULL)
          {
           start=n;
           start->lptr=NULL;
           last=n;
          }
          else
          {
           last->rptr=n;
           n->lptr=last;
           last=n;
          }

     }
} // End of Insert from Right 

//Insert in Between Nodes
void insert_between()
{

       struct node *n,*save;
       int k,pos;
       char o;
       n=(struct node*)malloc(sizeof(struct node));

       if(n==NULL)
       {
        cout<<"Overflow\n";
        getch();
       }
       else
       {
        cout<<"Item=";
        scanf("%d",&n->info);
        cout<<"Enter the position ---> ";
        scanf("%d",&pos);

             if(start==NULL && pos>1)
             {
              printf("\nYou can insert data only at the first position\
              as list is empty......\n");
              cout<<"Do you want insert at first position ? ---> ";
              scanf("%c",&o);
                   if(o=='y'||o=='Y')
                   {
                    start=n;
                    n->rptr=NULL;
                    n->lptr=NULL;
                    last=n;
                   }
                   else
                   {
                    exit(0);
                   }
              }
              else
              {
               save=start;
               k=1;
                   while(save!=NULL && k<pos-1)
                   {
                    save=save->rptr;
                    k++;
                   }
                   if(save==last&&k==pos-1)
                   {
                    n->lptr=last;
                    last->rptr=n;
                    last=n;             
                   }
                   else
                   {
                    save->rptr->lptr=n;
                    save->rptr->lptr->lptr=save;
                    save->rptr->lptr->rptr=save->rptr;
                    save->rptr=n;
                   }
               }
        }
}//End of Insert in between

// Delete from between
void delete_between()
{
     struct node *save,*temp;
     int pos,k;

        if(start==NULL)
        {
         cout<<"Underflow\n";
         exit(0);
        }
        else
        {
          cout<<"Give the position ---> ";
          scanf("%d",&pos);
           if(start->rptr==NULL)
           {
            save=start;
            start=NULL;
            last=NULL;
            free(save);
           }
           else
           {
            k=1;
            save=start;
               while(save!=NULL && k<pos-1)
               {
                save=save->rptr;
                k++;
               }
               if(start==last)
               {
                save=last;
                last=last->lptr;
                last->rptr=NULL;
               }
               else
               {
                temp=save->rptr;
                save->rptr->rptr->lptr=save;
                save->rptr=save->rptr->rptr;
                free(temp);
               }
           }
        }
}//End of Delete in between

// Delete from Left end
void delete_front()
{
     struct node *save;
         if(start==NULL)
         {
          cout<<"Empty List\n";
          getch();
         }
         else
         {
          save=start;
          start=start->rptr;
          start->lptr=NULL;
          free(save);
         }
}//End of Delete from front

// Delete from the Right End
void delete_end()
{
     struct node *save;
     if(start==NULL)
     {
      cout<<"Empty List\n";
      getch();
     }
     else
     {
         if(start->rptr==NULL)
         {
          save=start;
          start=NULL;
          free(save);
         }
         else
         {
          save=last;
          last=last->lptr;
          last->rptr=NULL;
          free(save);
         }
     }
}//End of Delete frm Right End

// Display the Elements
void view()
{
     struct node *save;
     if(start==NULL)
     {
      cout<<"No data available\n";
      getch();
     }
     else
     {
      save=start;
          while(save!=NULL)
          {
            printf("%d ",save->info);
            save=save->rptr;
          }
      }
}// End of Display 

// Main Function 
int main()
{
    int opinion,temp;
    //clrscr();
         do
         {
           cout<<"\nYou can do the following\n\n";
           cout<<"1.Insert_front\n2.Insert_end\n3.Insert Between\n";
           cout<<"4.Delete_front\n5.Delete_end\n6.Delete Between\n";
           cout<<"7.View\n8.Exit\n";
           cout<<"Opinion= ";
           scanf("%d",&opinion);
            switch(opinion)
            {
              case 1:insert_front();
              view();
              break;
              case 2:insert_end();
              view();
              break;
              case 3:insert_between();
              view();
              break;
              case 4:delete_front();
              view();
              break;
              case 5:delete_end();
              view();
              break;        
              case 6:
              {
                delete_between();
                view();
                break;
              }
              case 7:view();
              break;
              case 8:break;
              default:cout<<"Wrong Choice\n";
            }
         }
while(opinion!=8) ;
getch();
}
// End of Main 

[DeanMSands3]

There are multiple problems. I've got time for only a few.
In your insert_front() function you have this:

   if(n==NULL)
   {
    cout<<"\nOverflow\n";
    getch();
   }

It should have a return; statement inside it.

   if(n>=5)
    {
     delete_end();    
    }

This needs to be fixed. Here, you're trying to count the number of items. But n doesn't contain that. n is a pointer - a numerical address in memory. I'm more than certain that it will be getting a value bigger than 5. What you actually want to do is to insert the node (move the code out of the else block in front of the if; you don't need the else). Create an integer. Set it to 1. Move from node to node counting until you reach the end. If the number is bigger than 5, delete that node, decrement the number, and walk back. Keep doing until you have at most 5 blocks.

[srinivaskolli]

Thanks a lot DeanMSands3, i appreciate a lot.......
I will do that and try to execute.......

[srinivaskolli]

i did like this but it not working in a correct manner, can you pls correct it in this function.
thank you

int m=0;

    // Insert from Left End
    void insert_front()
    {
          struct node *n;
          n=(struct node*)malloc(sizeof(struct node));

           if(n==NULL)
           {
            cout<<"\nOverflow\n";
            getch();
           }
           else
           {
               cout<<"Item=";
               scanf("%d",&n->info);
               n->lptr=NULL;

                if (m<=5)
                {
                 m++;

                    if(start==NULL)
                    {
                     start=n;
                     last=n;
                     start->rptr=NULL;
                    }
                     else
                    {
                     n->rptr=start;
                     start->lptr=n;
                     start=n;
                    }
                 }

              else
              {
              delete_end(); 
              m=m-1; 
              last->rptr=n;
              n->lptr=last;
              last=n;  
              }
            }


    }// End of Insert from Left