jigi
BAN USERSenior MTS at Oracle Cloud
<pre lang="" line="1" title="CodeMonkey86821" class="run-this">class TwoStackMin {
private int top;
private int[] stackArr;
private int min_top;
private int[] sortedArr;
//constructor:
public TwoStackMin(int capacity) {
if(capacity<=0){
throw new IllegalArgumentException("Negative capacity value is illegal.");
}
stackArr = new int[capacity];
top=-1;
min_top = -1;
sortedArr = new int[capacity];
System.out.println("Created a new TwoStackMin object******************");
}
//pushing into stack and sotedStack: in O(1)
void push(int o){
if(stackArr.length == top){
throw new StackException("Stack overflow!");
}
stackArr[++top] = o;
if(min_top==-1){
sortedArr[++min_top]=o;
}
else{
if(o<sortedArr[min_top]){
sortedArr[++min_top] = o;
}
}
}
//pop() also in O(1):
void pop(){
if(top==-1){
throw new StackException("Empty stack!");
}
if(stackArr[top]==sortedArr[min_top]){
min_top-=1;
}
System.out.println(stackArr[top--]);
}
void peek(){
if(top==-1){
throw new StackException("Empty Stack!");
}
System.out.println(stackArr[top]);
}
boolean isEmpty(){
return top==-1;
}
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 emptyStack(){
if (top==-1){
throw new StackException("Stack is empty. Cannot clear the stack");
}
while(top!=-1){
System.out.println(stackArr[top--]);
}
while(min_top!=-1){
min_top--;
}
}
// min operation in O(1)
void min(){
System.out.println("The minimum value object is:"+sortedArr[min_top]);
}
}
</pre><pre title="CodeMonkey86821" input="yes">
TwoStackMin s1 = new TwoStackMin(10);
s1.push(4);
s1.push(2);
s1.min();
s1.push(7);
s1.push(3);
s1.push(1);
s1.min();
s1.pop();
s1.min();</pre>
Generalizing to k missing numbers. Single pass thru the array with XOR method.
- jigi March 21, 2013