Stack Implemetation with Push, Pop, GetMin and GetMax in constant time - Java
public class Stack {
int TOP = -1;
static final int MAX = 10;
int[] stack = new int[MAX];
public boolean isEmpty(){
if(TOP == -1)
return true;
else
return false;
}
public boolean isFull(){
if(TOP == MAX)
return true;
else
return false;
}
public int pop() {
int popEle = 0;
if (!isEmpty()) {
popEle = stack[TOP];
TOP--;
}
return popEle;
}
public void push(int ele){
if(!isFull()){
TOP = TOP + 1;
stack[TOP] = ele;
}
}
}
public class SpecialStack extends Stack {
Stack minStack = new Stack();
Stack maxStack = new Stack();
public void push(int ele){
if(isEmpty()){
super.push(ele);
minStack.push(ele);
maxStack.push(ele);
}else{
if(minStack.stack[TOP] > ele){
super.push(ele);
minStack.push(ele);
maxStack.push(maxStack.stack[TOP - 1]);
}else if(maxStack.stack[TOP] < ele){
super.push(ele);
maxStack.push(ele);
minStack.push(minStack.stack[TOP - 1]);
}
}
}
public int pop(){
minStack.pop();
maxStack.pop();
return super.pop();
}
public int getMin(){
int min = minStack.pop();
minStack.push(min);
return min;
}
public int getMax(){
int max = maxStack.pop();
maxStack.push(max);
return max;
}
public static void main(String[] args) {
SpecialStack s = new SpecialStack();
s.push(10);
s.push(2);
s.push(20);
s.push(30);
s.push(15);
System.out.println("Max "+s.getMax());
System.out.println("Min "+s.getMin());
s.push(5);
s.push(50);
System.out.println("Max "+s.getMax());
System.out.println("Min "+s.getMin());
}
}
o/p:
Max 30
Min 2
Max 50
Min 2
int TOP = -1;
static final int MAX = 10;
int[] stack = new int[MAX];
public boolean isEmpty(){
if(TOP == -1)
return true;
else
return false;
}
public boolean isFull(){
if(TOP == MAX)
return true;
else
return false;
}
public int pop() {
int popEle = 0;
if (!isEmpty()) {
popEle = stack[TOP];
TOP--;
}
return popEle;
}
public void push(int ele){
if(!isFull()){
TOP = TOP + 1;
stack[TOP] = ele;
}
}
}
public class SpecialStack extends Stack {
Stack minStack = new Stack();
Stack maxStack = new Stack();
public void push(int ele){
if(isEmpty()){
super.push(ele);
minStack.push(ele);
maxStack.push(ele);
}else{
if(minStack.stack[TOP] > ele){
super.push(ele);
minStack.push(ele);
maxStack.push(maxStack.stack[TOP - 1]);
}else if(maxStack.stack[TOP] < ele){
super.push(ele);
maxStack.push(ele);
minStack.push(minStack.stack[TOP - 1]);
}
}
}
public int pop(){
minStack.pop();
maxStack.pop();
return super.pop();
}
public int getMin(){
int min = minStack.pop();
minStack.push(min);
return min;
}
public int getMax(){
int max = maxStack.pop();
maxStack.push(max);
return max;
}
public static void main(String[] args) {
SpecialStack s = new SpecialStack();
s.push(10);
s.push(2);
s.push(20);
s.push(30);
s.push(15);
System.out.println("Max "+s.getMax());
System.out.println("Min "+s.getMin());
s.push(5);
s.push(50);
System.out.println("Max "+s.getMax());
System.out.println("Min "+s.getMin());
}
}
o/p:
Max 30
Min 2
Max 50
Min 2
Comments
Post a Comment