queue type data structure implementation using arrays

Question

I have undergone a situation where i have to implement a queue type data structure.It is like this:

(1) Suppose there is an array data[50]= {1,2,3,4,5,6};

(2) int Front must point to first index and int rear must point must point to last index.

(3)Now i have to add first and second element of this array. Suppose i do that (i+2=3) and this 3 will be set at last by doing rear+1 (data[rear+1]), Now when the second execution occurs, We don't have to take into account the first two element (they already added), So in this case we can do data[front+2]. But pay attention here please, because this +2 is going to be done first time only , after this it will be just +1 (because we added only one element, and first time we add 2 element).And the element obtained on addition must go to last of the index like "3" obtained will go at last like this {1,2,3,4,5,6,3}.

(4)So we have to take into account

(4.a) Increment of Rear by one on each addition.

(4.b) Increment of Front by one (accept the first addition where we add two elements).

(5) My idea to do this is as follows:

    #include <stdio.h>
    #define MAX 50
    int data[MAX];
    int rear = - 1;
    int front = - 1;

    void main()
    {
     int rear=6, front=0;
     data[size]={1,2,3,4,5,6};
     int count=size;
     //First do addition of the first two elements
     data[rear]= data[0]+data[1];
     for(i=front; i<size*2-1 ; i++) //we are doing data*2-1 because we know the final obtained on doing all the addition until there is 1 element will have the size (size*2-1).
      {
       do
        { 
         //here we do addition data[rear+1]=data[front]+data[rear];
         // rear++;     
         count--;
        }while (count>1);
       }
      for(i=0; i<size*2-1 ; i++)
      {
       printf("%d ", data[i]); //Now this must print "1,2,3,4,5,6,3,6,9,12,21" (addition of element at front and rear)
      }         

    }

**My doubt is how to increase the Front by two first time addition and by increasing by one after first addition so that first will always point to the element to be added(increasing is not difficult , i have done that). Please help me for Front increment, Algorithm and code will be very grateful.

There is no size, and there are multiple ways to address the problems of full-vs-empty detection in a circular buffer. Some of them here. — WhozCraig
– WhozCraig, Commented Feb 6, 2014 at 15:48
@WhozCraig sorry i am still not able to understand ,what you just said. Could you please explain me in detail. — user3206225
– user3206225, Commented Feb 6, 2014 at 16:11

Alex Johnson · Accepted Answer · 2014-02-06 18:40:44Z

1

int max = 50;
int index = 0;
int endIndex = 5; //You can compute the length. I will just hard code
int list[max] = {1,2,3,4,5,6};
int front = list[index];
int rear = list[endIndex];

while (index!= endIndex) 
{
if (index==0)
{
        index++;
        list[endIndex+index] = front+list[index];
        rear = list[endIndex+index];
        index++;
        front = list[index];
}
else 
{
        list[rear+1] = front + rear;
        index++;
        front = list[index];
        rear = list[endIndex+index];
}
}

This should do what are you are looking for. I didn't test it but I believe it is what you described.

edited Feb 6, 2014 at 18:40

answered Feb 6, 2014 at 15:58

Alex Johnson

5347 silver badges16 bronze badges

Sign up to request clarification or add additional context in comments.

5 Comments

user3206225 Over a year ago

Thanks for trying to help me, but your code will give output "3,4,5,6,0,0,0,0,0...." but the desire output is "1,2,3,4,5,6,3,6,10,15,21" (so i can't mark it correct for the moment).Help please :) , I think we need to use pointers because the way you telling we will loose the first two elements in the final list[size]; (I mean it will not display "1" and "2" as well). But i have to display them when i printf the list[size] but they should not take part in addition if they are added once.(I mean if 1+2=3, this 3 go at last like , 1234563 then front must point to "3" to add with the "3" at last)

user3206225 Over a year ago

and this Sizeof list will give the size of all the array (not number of elements), But no worries i can correct that.But the problem is what i mention in first comment, please try helping me in that. Thanks

Alex Johnson Over a year ago

I edited my previous submission. Sorry for the delay. I had some errors with some of my variables so I took one out, and hardcoded the length of the array. See if that might fix your problems.

user3206225 Over a year ago

the output from this code is { 1 0 3 4 6 6 0 0 0 0 0 0 }, still not correct :)

user3206225 Over a year ago

I finally done it, you can see below my full code. And thanks for trying to help me.

user3206225 · Accepted Answer · 2014-02-07 18:28:00Z

Finally i managed to solve the question, I am leaving here my code for others (if they use it in future):

#include <stdio.h>

void main()
{
int max = 50;
int index = 0,Front=0,Rear,min,min2,location,i,location2,flag[30],check=0,j;

int data[50] = {1,2,3,4};
 Rear=3;
//Rear=size-1
for(i=0; i<=Rear;i++)
{
flag[i]=0;
 //printf("");
 }
int count=Rear;
do
{
//printf("check5 \n ");
if(Front==0)
 {
printf("check1 \n ");

Rear++;
 data[Rear]=data[Front] +data[1];
    flag[Front]=1;
    flag[Rear]=0;
        flag[1]=1;
 printf("datafront: %d\n ", data[Front]);
  printf("*****************dataRear: %d\n ", data[Rear]);
 printf("Front : %d\n ", Front);
printf("Rear : %d \n", Rear);
 //printf("flagRear: %d\n ", flag[Front]);
Front=Front+2; 
//Rear++;
 }

   if(data[Front]==data[Rear] && flag[Rear] ==0 && flag[Front]==0 ) 
 { 
    printf("check3 \n ");
     printf("Front : %d\n ", Front);
    // Rear++;
printf("Rear : %d \n", Rear);
printf("dataFront1: %d\n ", data[Front]);
printf("dataRear1: %d\n ", data[Rear]);
    data[Rear+1]= data[Front] +data[Rear];
    printf("************dataRear[Rear+1]: %d\n ", data[Rear+1]);
    flag[Front]=1;
    flag[Rear]=1;
    flag[Rear+1]=0;
    printf("check Front front : %d\n", Front);
                for(j=Front+1;j<=Rear;j++)
                {
                if(flag[j]==0)
                {
                Front=j;    
                 break;             
                }
                }           
//  Front++; 
    Rear++;
}

  if(data[Front]<data[Rear] && flag[Rear] ==0 && flag[Front]==0) 
   {         
         printf("check4 \n ");   
                 printf("Front : %d\n ", Front);
printf("Rear : %d \n", Rear);
printf("dataFront1: %d\n ", data[Front]);
printf("dataRear1: %d\n ", data[Rear]);
 printf("Flagcheck data[6].flag : %d \n",flag[6]);
                int start= Front+2;
                min= data[Front];
                for(j=Front+1;j<=Rear;j++)
                {
                if(flag[j]==0)
                {
                min2=data[j];
                location2=j;
                printf("j = %d \n",j);
                break;
                }
                }
                location=Front;

                 for(i=start;i<=Rear;i++) 
                {
                    if (data[i] <min && flag[i]==0) 
                    {
                        min=data[i];
                        location=i;     
                        min2=min;   
                    }
                    if (data[i]<min2&& flag[i]==0) 
                    {
                        min2=data[i];
                        location2=i;
                    }       
                }
                data[Rear+1]= min2+min; 
                printf("min= %d\n", min);
                printf("min2= %d\n", min2);
                printf("location= %d\n", location);
                printf("location2= %d\n", location2);
                printf(" ***********data[Rear+1] = %d\n", data[Rear+1]);
                flag[location2]=1;
                flag[location]=1;
                flag[Rear+1]=0;

                for(j=location+1;j<=Rear;j++)
                {
                if(flag[j]==0)
                {
                Front=j;    
                 break;             
                }
                }           
                Rear=Rear+1;                
 printf("Front : %d\n ", Front);
printf("Rear : %d \n", Rear);
 }  
//printf("\n");
//printf("Front : %d\n ", data[Front]);
//printf("Rear : %d \n", data[Rear]);
count--;
} while(Front!=Rear && count>0);
for (i=0;i<15;i++)
{
 printf(" %d  ", data[i]);
}
//char path[100]={'\0'};
//traverse_tree(data, 10,path);
printf("\n");
}
////

Collectives™ on Stack Overflow

queue type data structure implementation using arrays

2 Answers 2

5 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

5 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related