Я выкладываю полный код здесь, чтобы найти min и mx в стеке.
Временная сложность составит O (1)
пакет com.java.util.collection.advance.datastructure;
/ **
*
* @author vsinha
*
* /
открытый абстрактный интерфейс Stack {
/**
* Placing a data item on the top of the stack is called pushing it
* @param element
*
*/
public abstract void push(E element);
/**
* Removing it from the top of the stack is called popping it
* @return the top element
*/
public abstract E pop();
/**
* Get it top element from the stack and it
* but the item is not removed from the stack, which remains unchanged
* @return the top element
*/
public abstract E peek();
/**
* Get the current size of the stack.
* @return
*/
public abstract int size();
/**
* Check whether stack is empty of not.
* @return true if stack is empty, false if stack is not empty
*/
public abstract boolean empty();
}
пакет com.java.util.collection.advance.datastructure;
@ SuppressWarnings ( "прятались")
открытый абстрактный интерфейс MinMaxStack расширяет стек {
public abstract int min();
public abstract int max();
}
пакет com.java.util.collection.advance.datastructure;
import java.util.Arrays;
/ **
*
* @author vsinha
*
* @param
* /
открытый класс MyStack реализует стек {
private E[] elements =null;
private int size = 0;
private int top = -1;
private final static int DEFAULT_INTIAL_CAPACITY = 10;
public MyStack(){
// If you don't specify the size of stack. By default, Stack size will be 10
this(DEFAULT_INTIAL_CAPACITY);
}
@SuppressWarnings("unchecked")
public MyStack(int intialCapacity){
if(intialCapacity <=0){
throw new IllegalArgumentException("initial capacity can't be negative or zero");
}
// Can't create generic type array
elements =(E[]) new Object[intialCapacity];
}
@Override
public void push(E element) {
ensureCapacity();
elements[++top] = element;
++size;
}
@Override
public E pop() {
E element = null;
if(!empty()) {
element=elements[top];
// Nullify the reference
elements[top] =null;
--top;
--size;
}
return element;
}
@Override
public E peek() {
E element = null;
if(!empty()) {
element=elements[top];
}
return element;
}
@Override
public int size() {
return size;
}
@Override
public boolean empty() {
return size == 0;
}
/**
* Increases the capacity of this <tt>Stack by double of its current length</tt> instance,
* if stack is full
*/
private void ensureCapacity() {
if(size != elements.length) {
// Don't do anything. Stack has space.
} else{
elements = Arrays.copyOf(elements, size *2);
}
}
@Override
public String toString() {
return "MyStack [elements=" + Arrays.toString(elements) + ", size="
+ size + ", top=" + top + "]";
}
}
пакет com.java.util.collection.advance.datastructure;
/ **
* Сложность времени будет O (1), чтобы найти минимальное и максимальное значения в данном стеке.
* @author vsinha
*
* /
Открытый класс MinMaxStackFinder расширяет MyStack и реализует MinMaxStack {
private MyStack<Integer> minStack;
private MyStack<Integer> maxStack;
public MinMaxStackFinder (int intialCapacity){
super(intialCapacity);
minStack =new MyStack<Integer>();
maxStack =new MyStack<Integer>();
}
public void push(Integer element) {
// Current element is lesser or equal than min() value, Push the current element in min stack also.
if(!minStack.empty()) {
if(min() >= element) {
minStack.push(element);
}
} else{
minStack.push(element);
}
// Current element is greater or equal than max() value, Push the current element in max stack also.
if(!maxStack.empty()) {
if(max() <= element) {
maxStack.push(element);
}
} else{
maxStack.push(element);
}
super.push(element);
}
public Integer pop(){
Integer curr = super.pop();
if(curr !=null) {
if(min() == curr) {
minStack.pop();
}
if(max() == curr){
maxStack.pop();
}
}
return curr;
}
@Override
public int min() {
return minStack.peek();
}
@Override
public int max() {
return maxStack.peek();
}
@Override
public String toString() {
return super.toString()+"\nMinMaxStackFinder [minStack=" + minStack + "\n maxStack="
+ maxStack + "]" ;
}
}
// Тестовая программа
пакет com.java.util.collection.advance.datastructure;
import java.util.Random;
открытый класс MinMaxStackFinderApp {
public static void main(String[] args) {
MinMaxStack<Integer> stack =new MinMaxStackFinder(10);
Random random =new Random();
for(int i =0; i< 10; i++){
stack.push(random.nextInt(100));
}
System.out.println(stack);
System.out.println("MAX :"+stack.max());
System.out.println("MIN :"+stack.min());
stack.pop();
stack.pop();
stack.pop();
stack.pop();
stack.pop();
System.out.println(stack);
System.out.println("MAX :"+stack.max());
System.out.println("MIN :"+stack.min());
}
}
Выход:
MyStack [elements = [99, 76, 92, 49, 89, 88, 93, 33, 0, 30], размер = 10, top = 9]
MinMaxStackFinder [minStack = MyStack [elements = [99, 76, 49, 33, 0, ноль, ноль, ноль, ноль, ноль], размер = 5, топ = 4]
maxStack = MyStack [elements = [99, ноль, ноль, ноль, ноль, ноль, ноль, ноль, ноль, ноль, ноль], размер = 1, верх = 0]]
МАКС: 99
MIN: 0
MyStack [elements = [99, 76, 92, 49, 89, null, null, null, null, null], size = 5, top = 4]
MinMaxStackFinder [minStack = MyStack [elements = [99, 76, 49, ноль, ноль, ноль, ноль, ноль, ноль, ноль], размер = 3, верх = 2]
maxStack = MyStack [elements = [99, ноль, ноль, ноль, ноль, ноль, ноль, ноль, ноль, ноль, ноль], размер = 1, верх = 0]]
МАКС: 99
MIN: 49
Дайте мне знать, если у вас возникнут проблемы.
Спасибо,
ВИКАШ СИНХА