CareerCup

see one thing is there
u have to either compromise with the pop operation or the push operation

Just use two stacks for this.

For push - push into first stack always. Into second stack, push if it is empty or the value is lesser than peek(second stack).

For pop - Pop(first stack). If value that has been popped = peek(second stack), then pop(second stack).

For min - just peek(second stack).

O(1) for push, pop and min.

<pre lang="" line="1" title="CodeMonkey28868" class="run-this">package StackDemo;

class Stack {
private int top;
private int[]stackArr;
private int minObj;

Stack(int capacity) throws IllegalArgumentException{
if(capacity <= 0){
throw new IllegalArgumentException("Capacity has to be a positive number");
}
top = -1;
stackArr = new int[capacity];

}

void push(int s){
if(stackArr.length == top){
throw new StackException("Stack's storage is overflowing");
}

stackArr[++top]=s;
if(top==0){
minObj=stackArr[0];
}
if(s<minObj){
minObj=s;
}

}

void pop(){
if (top == -1) {

throw new StackException("Stack is empty");
}
if(minObj==stackArr[top]){
int i=top-1;
int secondminObj = stackArr[i];
while(i>0){
if(stackArr[--i]<secondminObj){
secondminObj=stackArr[i];
}
}

minObj=secondminObj;
}
System.out.println(stackArr[top--]);



}

void peek(){
if (top == -1) {

throw new StackException("Stack is empty");
}
System.out.println(stackArr[top]);

}

boolean isEmpty(){

return top==-1;
}

void emptyStack(){

if (top==-1){
throw new StackException("Stack is empty. Cannot clear the stack");
}
while(top!=-1){
System.out.println(stackArr[top--]);
}

}

boolean search(int obj){
if(top==-1){

throw new StackException("Stack is empty");
}
boolean found = false;
for(int i=0;i<=top;i++){
if(stackArr[i]==obj){
found = true;
break;
}
}
return found;
}


void min(){

System.out.println("The minimum value object is:"+minObj);
}



}

</pre><pre title="CodeMonkey28868" input="yes">
</pre>

Here is the code with two stack used and one with min stack.
{{
public class StackWithMin {
int MAX_ELEMENT = 20;
int[] origStack = new int[MAX_ELEMENT];
int[] minStack = new int[MAX_ELEMENT];
int origStackTopIndex =-1 ;
int minStackTopIndex =-1;

public void push(int element) throws Exception{
if (origStackTopIndex ==MAX_ELEMENT ) throw new Exception("Stack is full. Max element "+MAX_ELEMENT);
origStack[++origStackTopIndex] = element;
if (origStackTopIndex == 0 || element<= minStack[minStackTopIndex] )
minStack[++minStackTopIndex] = element;

}
public int peek(){
return origStack[origStackTopIndex] ;
}
public int pop() throws Exception{
if (origStackTopIndex == -1) throw new Exception ("Stack is already empty");
if (origStack[origStackTopIndex] == minStack[minStackTopIndex] ) --minStackTopIndex;
return origStack[origStackTopIndex--];
}
public int min(){
return minStack[minStackTopIndex];
}

}


}}
git location

{{
@git httr01/algorithms/blob/master/src/main/java/com/algo/amazon/stack
}}