SortableStack implementation in Java

I am implementing an interface for Stack which will help to push and pop in O(n) time and help in finding the highest, lowest and the middle element in O(1) time.


I will be using Arraylist (since I m using a standard jdk 6 and not some other package) because with using this we can implement the above interface in the least possible time.



The above time complexity can be lowered even more by using Treelist, but since it doesn't comes under standard java 6 thats why we are using arraylist. Treelist can be used by download the commons.apache.*; package.


The code for implementing the Stack interface :


Interface :

package jp.co.worksap.intern;

public interface IsStack<E extends Comparable<E>> {

    public void push(E e);
    
    public E pop();
    
    public E peekMidElement();
    
    public E peekHighestElement();
    
    public E peekLowestElement();
    
    public int size();
    
}

SortableStack Class :

package jp.co.worksap.intern;

import java.util.ArrayList;
import java.util.Collections;
import java.util.EmptyStackException;


public class SortableStack<E extends Comparable<E>> 

implements ISortableStack<E>{

    
    private ArrayList<E> list = new ArrayList<E>();
    private ArrayList<E> Sortedlist = new ArrayList<E>();
    
    @Override
    public E peekHighestElement() {        
        if(size()<=0){
            throw new EmptyStackException();
        }
        return Sortedlist.get(size()-1);
    }

    @Override
    public E peekLowestElement() {
        if(size()<=0){
            throw new EmptyStackException();
        }
        return Sortedlist.get(0);
    }

    @Override
    public E peekMidElement() {     
        if(size()<=0){
            throw new EmptyStackException();
        }
        int mid=(size()-1)/2;
        return Sortedlist.get(mid+1);
    }

    @Override
    public E pop() {         
        if(size()<=0){
            throw new EmptyStackException();
        }
        E e=list.remove(size()-1);
        Sortedlist.remove(e);
        return e;
    }

    @Override
    public void push(E e) {        
        if(e==null) throw new EmptyStackException();
        
        int index=Collections.binarySearch(Sortedlist, e); //It returns index of the search key, if it is contained in the list; otherwise, (-(insertion point) - 1).
        index=index < 0 ?(Math.abs(index)-1):index;
        list.add(e);
        Sortedlist.add(index,e);
    }

    @Override
    public int size() {
        return list.size();
    }
    
}

To Check more posts on JAVA, CLICK HERE