CareerCup

Use a queue which will have enqueue() and dequeue() operations.

Also, there would be a stack which would contain all max elements encountered till now.

Whenever an element is being enqueued, and it is greater than current max (top of stack), it will be pushed on stack also.

If a no. 'k' is current max and 'k' comes for enqueueing once again we will push 'k' once more on stack.

Whenever we dequeue an element, we check if it is same as element on top of stack. If it is same pop the element from stack as well.

use heap to heapify the elements of the queue..i,e when you enQ put in heap, the max can be retrieved from max heap in O(1). when u deQ, deQ it from the heap also.

So enQ is O(logn), deQ is O(logn) and findMax is O(1).

So what is the question?

You can have a variable max. During each enqueue() you can compare it with max and change it accordingly. Whenever max is dequeued perform a sorting algorithm and assign the max value ?

int arr[n],n=0,c=0;
enqueue()
{
scanf("%d",c);
for(i=n;i<0;i--)
arr[n+1] = arr[n];
arr[0] = c;
n++;
}
dequeue()
{
free(arr[n]);
n--;
}
findmax()
{
c = 0;
for(i=n;i>0;i--)
if( c < arr[n]){ c = arr[n];}
printf("max = %d",c);
}


voidmain()
{
printf("enter number to insert or delete or find max -1 to exit");
scanf("%d",c);
if(C!=-1)
queue()
{
if(c ==1)
enqueue();
if(c==2)
dequeue();
if(c==3)
findmax()
else{
printf("enter number to insert or delete or find max -1 to exit");
scanf("%d",c);
queue();
}
}

we can also implement it by the use of two queues,one cud be used as the normal queue and the other cud be used as the queue for storing the maxelements...

Instead of storing the values straight away create an object with something like

class Data
{
int number;
int maxValue;
}
Queue<Data> q = new LinkedList<Data>();
Every time you store your values, store it as this Data object
so
enqueue(int value)
{
Data data = new Data();
data.number = value;
if(data.maxValue < value)
data.maxValue = value;
}

What this does is it stores the findMax at each point of the data insertion, so you can access the maximum data at each point looking at the top of the queue.

If it were a Stack, then using two stacks would have made sense. But since it is a queue and queue is a FIFO (not a LIFO). You may use a single variable to keep track of the max and at each insertion compare the new element with max and update max accordingly. If a dequeue is performed, the element that was inserted first will be removed. finding max will be O(1) time.