Showing posts with label circular. Show all posts
Showing posts with label circular. Show all posts

Thursday, January 3, 2013

Implementing Circular Queue in C


Not full working code, but you get the idea
elements are inserted clockwise, deleted clockwise.

Basic conditions :
If rear is one position to the left of front --> queue is empty
If rear is two positions to the left of front --> queue is full

So the array of size n holds only n-1 elements at a time, so as to differentiate queue-empty and queue-full scenarios.

---------------------------------------------------------------------------------------------

front = 0;
rear = n - 1;
int A[n];

void enqueue(int elem){
if((rear+front+2)%n == 0){
printf("Queue is full");
return;
}
rear = (rear+1)%n;
A[rear] = elem;
}

int dequeue(){
if((front-rear+n)%n == 1){
printf("Queue is empty");
return;
}
int temp = A[front];
front = (front+1)%n;
return temp;
}

Monday, August 13, 2012

Maximum contiguous sum in Circular Array


// find max contiguous sum in circular array
// INPUT : {8,-8,9,-9,10,-11,12} OUTPUT : 22
// INPUT : {1,-1,2,-1,1} OUTPUT : 3

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

int findMaxContSum(int A[],int len){
int i,c,max;
for(i=0;i<len;i++){
//printf("%d\n",A[i]);
}
int *S = (int *)malloc(sizeof(int)*len);
int *start = (int *)malloc(sizeof(int)*len);
for(i=0;i<len;i++){
start[i] = -1;
}
S[0] = A[0];
start[0] = 0;
for(i=1;;i=(i+1)%len){
c = (i-1+len)%len;
if(start[i] == start[c]){
break;
}
if(S[c] + A[i] > A[i]){
S[i] = S[c] + A[i];
start[i] = start[c];
} else {
S[i] = A[i];
start[i] = i;
}
}
max = S[0];
for(i=1;i<len;i++){
if(S[i] > max){
max = S[i];
}
}
free(start);
free(S);
return max;
}

int main(){
//int A[] = {8,-8,9,-9,10,-11,12};
int A[] = {1,-1,2,-1,1};
int max = findMaxContSum(A,sizeof(A)/sizeof(int));
printf("%d",max);
return 0;
}