Homework SourseDesign a stack that supports a max operation The max operati
Design a stack that supports a max operation. The max operation will return the maximum value of the data stored in the stack. Assume data values are int.
Output: Max value in stack
Constraints on the code: Do not use any Java objects or classes beyond char stream I/O. Do not use Stack.
Also, we are not allowed to violate the stack or damage it when finding the max of the stack.
Please help me.
Solution
Hi, friend please find my code.
Please let me know in case of any issue.
Use two stacks: one to store actual stack elements and other as an auxiliary stack to store maximum values. The idea is to do push() and pop() operations in such a way that the top of auxiliary stack is always the maximum. Let us see how push() and pop() operations work.
Push(int x) // inserts an element x to Special Stack
1) push x to the first stack (the stack with actual elements)
2) compare x with the top element of the second stack (the auxiliary stack). Let the top element be y.
…..a) If x is greater than y then push x to the auxiliary stack.
…..b) If x is smaller and equal than y then push y to the auxiliary stack.
int Pop() // removes an element from Special Stack and return the removed element
1) pop the top element from the auxiliary stack.
2) pop the top element from the actual stack and return it.
The step 1 is necessary to make sure that the auxiliary stack is also updated for future operations.
int getMax() // returns the maximum element from Special Stack
1) Return the top element of auxiliary stack
######################## Stack.java ##################
public class Stack{
int [] items; // actual stack
int [] aux; // auxiliary stack to store the maximum element
int top ; // denotes top of stack
// constructor
public Stack(int size){
items = new int[size];
aux = new int[size];
top = -1;
}
// push operation
public void push(int d){
// if stack is full
if (top == items.length - 1){
System.out.println(\"No space left for element \"+d);
return;
}
// if stack is empty
if(top == -1) {
aux[top+1] = d;
items[top+1] = d;
}
else{
// if d is greater than top of auxiliary stack, then add d in both stack
if(d > aux[top]){
aux[top+1] = d;
items[top+1] = d;
}
else{ // if d <= top of auxiliary stack
aux[top+1] = aux[top];
items[top+1] = d;
}
}
top++;
}
public int getMax(){
return aux[top];
}
public int peek(){
return items[top];
}
public int pop(){
if (top == -1){
//System.out.println(\"No element in stack\");
return -1;
}
return items[top--];
}
}
################# MaxStackTest.java ##############
public class MaxStackTest{
public static void main(String [] args){
Stack s = new Stack(10);
s.push(50);
s.push(40);
System.out.println(\"Max = \" +s.getMax());
s.push(30);
s.push(20);
System.out.println(\"Max = \" +s.getMax());
s.push(100);
s.push(70);
System.out.println(\"Max = \" +s.getMax());
s.push(120);
s.push(90);
System.out.println(\"Max = \" +s.getMax());
do{
int temp = s.pop();
if (temp == -1) break;
System.out.print(temp + \" \");
}while(true);
}
}
/*
Sample Output:
Max = 50
Max = 50
Max = 100
Max = 120
90 120 70 100 20 30 40 50
*/
