Question

Design a stack class by importing the available java.util.Stack to have the following features:

• push(x) -- push element x onto stack, where x is anywhere between Integer.MIN_VALUE and Integer.MAX_VALUE.
• pop() -- remove the element on top of the stack.
• top() -- get the top element.
• getMax() -- retrieve the max element in the stack in constant time (i.e., O(1)).

Your code should have the following shape and form, all in one .java file. Note the styling and documentation API already included for the target class, MaxStack:

import java.util.Stack;
public class HomeworkAssignment1_1 {   
    public static void main(String[] args) {
       // Your main() is not graded so you can
       // have any implementation in this area
       MaxStack obj = new MaxStack();
       obj.push(12);
       obj.push(1);
       obj.push(-12);
       obj.pop();
       System.out.println(obj.top());
       System.out.println(obj.getMax());
       // etc.
   }
}
/**

* The MaxStack program implements a Stack class with the following features:
* push(x) -- push element x onto stack
* pop() -- remove the element on top of the stack
* top() -- get the top element.
* getMax() -- retrieve the max element in the stack in constant time (i.e., O(1)

*/
class MaxStack {
   // Initialize your data structure in constructor
   // or here; choice is yours.

   public MaxStack() { // YOUR CODE HERE }

public void push(int x) { // YOUR CODE HERE }
   public void pop() { // YOUR CODE HERE }
   public int top() { // YOUR CODE HERE }
   public int getMax() { // YOUR CODE HERE }
}

EXAMPLES

MaxStack maxStack = new MaxStack();

maxStack.push(-2);

maxStack.push(0);

maxStack.push(-3);

maxStack.getMax(); // returns 0

maxStack.pop();

maxStack.top(); // returns 0

maxStack.getMax(); // returns 0

CONSTRAINTS AND ASSUMPTIONS

• For this problem you are ONLY allowed to use Java's reference class Stack (Links to an external site.). Failure to do so will receive 5 points off.
• MaxStack does not mean elements have to be ordered in increasing or decreasing values in the Stack.

HINTS

• You solution should persist a global max value while maintaining the ability to transact on a java.util.Stack instance wrapped in your MaxStack class.
• When implementing the MaxStack methods, you will have to invoke your Java stack instance's comparable methods (naming convention may be different).

Answer 1

//name the file HomeworkAssignment_1

import java.util.Stack;

public class HomeworkAssignment1_1 {

static class MaxStack

{

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

int maxEle;

void getMax()

{

if (s.empty())

System.out.print("Stack is empty\n");

// variable maxEle stores the maximum element

// in the stack.

else

System.out.println(maxEle);

}

// Prints top element of MyStack

void top()

{

if (s.empty())

{

System.out.println("Stack is empty ");

return;

}

int t = s.peek(); // Top element.

// If t < maxEle means maxEle stores

// value of t.

if(t > maxEle)

System.out.println(maxEle);

else

System.out.println(t);

}

// Remove the top element from MyStack

void pop()

{

if (s.empty())

{

System.out.println("Stack is empty");

return;

}

int t = s.peek();

s.pop();

// Maximum will change as the maximum element

// of the stack is being removed.

if (t > maxEle)

{

maxEle = 2 * maxEle - t;

}

}

// Removes top element from MyStack

void push(int x)

{

// Insert new number into the stack

if (s.empty())

{

maxEle = x;

s.push(x);

return;

}

// If new number is less than maxEle

if (x > maxEle)

{

s.push(2 * x - maxEle);

maxEle = x;

}

else

s.push(x);

}

};

public static void main(String[] args) {

// have any implementation in this area

MaxStack maxStack = new MaxStack();

maxStack.push(-2);

maxStack.push(0);

maxStack.push(-3);

maxStack.getMax(); // returns 0

maxStack.pop();

maxStack.top(); // returns 0

}

}

Answer 2

To implement the MaxStack class with the specified features, we need to use the Java Stack class and maintain a global max value while performing the push, pop, top, and getMax operations.

Here's the complete MaxStack class implementation:

javaCopy codeimport java.util.Stack;/**
 * The MaxStack program implements a Stack class with the following features:
 * push(x) -- push element x onto stack
 * pop() -- remove the element on top of the stack
 * top() -- get the top element.
 * getMax() -- retrieve the max element in the stack in constant time (i.e., O(1))
 */class MaxStack {    private Stack<Integer> stack;    private int max;    public MaxStack() {
        stack = new Stack<>();
        max = Integer.MIN_VALUE;
    }    public void push(int x) {        if (x > max) {
            stack.push(2 * x - max); // Store an encoded value to track the maximum element
            max = x;
        } else {
            stack.push(x);
        }
    }    public void pop() {        if (stack.isEmpty()) {            return;
        }        int popped = stack.pop();        if (popped > max) {
            max = 2 * max - popped; // Decode the stored encoded value to get the previous maximum
        }
    }    public int top() {        if (stack.isEmpty()) {            return -1; // Return a default value indicating an empty stack
        }        int peeked = stack.peek();        if (peeked > max) {            return max; // Return the maximum value instead of the encoded value
        } else {            return peeked;
        }
    }    public int getMax() {        return max;
    }
}public class HomeworkAssignment1_1 {    public static void main(String[] args) {        MaxStack obj = new MaxStack();
        obj.push(12);
        obj.push(1);
        obj.push(-12);
        obj.pop();
        System.out.println(obj.top()); // Output: 1
        System.out.println(obj.getMax()); // Output: 12
    }
}

Explanation:

• The MaxStack class uses a Java Stack to store the elements.

• We maintain a global variable max to keep track of the maximum element in the stack.

• In the push method, we compare the new element with the current maximum. If the new element is greater than the current maximum, we store an encoded value on the stack and update the maximum. Otherwise, we directly push the new element onto the stack.

• In the pop method, we check the top element of the stack. If it is greater than the current maximum, we decode the stored encoded value to get the previous maximum.

• In the top method, we check the top element of the stack. If it is greater than the current maximum, we return the current maximum as it is the actual top element. Otherwise, we return the element as it is.

• The getMax method simply returns the current maximum value.

This implementation allows us to perform the getMax operation in constant time (O(1)) without sacrificing the efficiency of other operations.