#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

doesnt work..check i/p push : 1 3 5 2 4 8try out max till stack empty