optimal implementation for max() operation in a Stack

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

typedef struct
{
int data;
int nextMax;

}StackNode;

typedef struct
{
int top;
int max;
int size;

StackNode *arr;

}Stack;

void init(Stack *s, int size)
{
if(s == NULL) return;

memset(s, 0, sizeof(Stack));

s->size = size;
s->arr = calloc(size, sizeof(StackNode));
}

inline int isFull(Stack *s)
{
return s == NULL || s->top >= s->size;
}

inline int isEmpty(Stack *s)
{
return s == NULL || s->top == 0;
}


int push(Stack *s, int d)
{
if(isFull(s))
return -1;

s->arr[s->top].data = d;

if(s->arr[s->max].data < d)
{
s->arr[s->top].nextMax = s->max;
s->max = s->top;
}
s->top++;
return 0;
}

int pop(Stack *s, int *d)
{
if(isEmpty(s))
return -1;

s->top--;

*d = s->arr[s->top].data;

if(s->max == s->top)
{
s->max = s->arr[s->top].nextMax;
}

return 0;
}

int max(Stack *s, int *m)
{
if(isEmpty(s))
return -1;

*m = s->arr[s->max].data;

return 0;
}

int main()
{
int n;

scanf("%d", &n);

int i;

Stack s;

init(&s, n);
int m;

for(i = 0 ; i < n; ++i)
{
scanf("%d", &m);

push(&s, m);
}

int code ;

do
{
scanf("%d", &code);

switch(code)
{
case 1:
{
scanf("%d", &m);

push(&s, m);
}
break;
case 2:
pop(&s, &m);
break;
case 3:
max(&s, &m);
printf("%d\n", m);
break;
}
}while(code != 4);

}
Advertisements

One thought on “optimal implementation for max() operation in a Stack

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s