Track the Maximum Element in a Stack. | Algorithms

Track the Maximum Element in a Stack. | Algorithms
In a Stack, keep track of max­i­mum value in it. It might be the top ele­ment in the stack but once it is poped out, the max­i­mum value should be from the rest of the ele­ments in the stack.

    Stack<Integer> main = new Stack<>();

    Stack<Integer> track = new Stack<>();

 

    public void insert(int x) {

        if (main.isEmpty()) { // if stack is empty, insert the number in both

                                // stacks

            main.add(x);

            track.add(x);

        } else {

            // check if number in Stack(track) is bigger than x

            // which ever is bigger, insert it into Stack

 

            int a = track.peek();

            track.add(Math.max(a, x));

            main.add(x); // insert it into main stack.

        }

    }

 

    public int remove() {

        if (!main.isEmpty()) { // pop the top elements

            track.pop();

            return main.pop();

        }

        return 0;

    }

 

    public int getMax() {

        return track.peek();

    }

http://www.geeksforgeeks.org/design-and-implement-special-stack-data-structure/
Space Optimized Version

void SpecialStack::push(int x)

{

    if(isEmpty()==true)

    {

        Stack::push(x);

        min.push(x);

    }

    else

    {

        Stack::push(x);

        int y = min.pop();

        min.push(y);

  

        /* push only when the incoming element of main stack is smaller

        than or equal to top of auxiliary stack */

        if( x <= y )

          min.push(x);

    }

}

 

/* SpecialStack's member method to remove an element from it. This method

   removes top element from min stack also. */

int SpecialStack::pop()

{

    int x = Stack::pop();

    int y = min.pop();

 

    /* Push the popped element y  back only if it is not equal to x */

    if ( y != x )

      min.push(x);

 

    return x;

}

Read full article from Track the Maximum Element in a Stack. | Algorithms