In this part of the assignment, you will implement an ADT called MaxStack. It mu

ID: 3739089 • Letter: I

Question

In this part of the assignment, you will implement an ADT called MaxStack. It must implement the following API (note that we are not defining the API as an interface here): public class MaxStack> MaxStack ) constructor add x to the top of the stack remove and return the top element return the maximum value in the stack void push (T x) T pop () T getMax ) In other words, it's similar to a regular stack, but you can always quickly find the maximum element. Here is a sample client you can use for testing: public static void main(Stringl] args) ( MaxStack ms new MaxStack(); ms.push( 2) Stdout.printIntms.getMax()); // should print 2 ms.push( 3); Stdout.printin(ms.getMax()); I1 should print 3 ms.push(1); stdout.printIn(ms.getMax(;/should print 3 ms.push(3); Stdout.print Intms.getMax( / should print 3 ms.pop() Stdout.printIn(ms.getMax()) 11 should print 3 ms pop(); Stdout.println(ms.getMax()); 11 should print 3 ms.pop); Stdout.println(ms.getMax()); // should print 2 You cannot implement getMax () by searching the stack looking for the largest element. The maximum element must be readily available without searching the stack. You can assume that the Maxstack instance has at least one item any time pop () or getMax () is called. Also, getMax () does not change the stack contents.

Explanation / Answer

In the above code you are updating stk with latest values but stk2 is not updated same time. It should be updated too with latest pushed value and at the same time you wanted to have only one entry in stk2, so we need to pop value all the time based on condition. below is the executed code.

import java.util.*;

import java.lang.*;

import java.io.*;

public class MaxStack <T extends Comparable <T>> {

Stack<T> stk= new Stack<T>();

Stack<T> stk2= new Stack<T>();

T x;

//add x to the top of the stack

void push (T x) {

if(stk2.size() != 0) {

if(stk2.peek <= x){

stk2.pop();

}

if(stk.isEmpty()) {

stk.push(x);

stk2.push(x);

}

else

if(stk.peek().compareTo(stk2.peek())>0){

}

stk.push(x);

stk2.push(x);

}

//remove and return the top element

T pop() {

return stk.pop();

}

//retunr the maximum value in the stack

T getMax() {

//Returns (but does not remove) the item most recently added to this stack.

return stk2.peek();

}

public static void main (String[] args) {

MaxStack<Integer> ms = new MaxStack<Integer>();

ms.push(2);