java 模拟栈 需要一个最优算法（在线等）

Question

想实现这个接口，想用一个最优的算法。
1.E的类型不确定，无论什么类型，需要重写compareTo()吗？若需要，如何实现？
2.最大最小还有中间值，有什么优一些的算法？（尤其中间值）在线等！！！！！谢谢各位！
可自定义方法！
public interface Stack<E extends Comparable<E>> {

//入栈
public void push(E e);


//出栈
public E pop();


//找到栈中第size/2+1小的值，但不删除此数据
public E peekMedian();


//找到栈中最大值，但不删除此数据
public E peekMaximum();


//找到栈中最小值，但不删除此数据
public E peekMinimum();


//返回栈的长度
public int size();}

Answer 1

你用LinkedList直接写就是了。它的算法就是最好的。
package com.neil.tools;import java.util.LinkedList;/**
 * 自定义栈
 * @author neil
 * @date 2011-9-17
 * @fileName MyStack.java
 * @packageName com.neil.expression
 */
public class MyStack<T> {
/** 栈 */
private LinkedList<T> stackStorage;
/**
 * 压栈
 * @param v 压入元素
 */
public void push(T v){
this.stackStorage.addFirst(v);
}
/**
 * 得到栈顶元素
 * @return
 */
public T peek(){
return this.stackStorage.getFirst();
}
/**
 * 出栈
 * @return 栈顶元素
 */
public T pop(){
return this.stackStorage.removeFirst();
}
/**
 * 判断栈是否为空
 * @return 
 */
public boolean isEmpty(){
return this.stackStorage.isEmpty();
}

@Override
public String toString(){
return this.stackStorage.toString();
}
}

Answer 2

想实现这个接口，想用一个最优的算法。
1.E的类型不确定，无论什么类型，需要重写compareTo()吗？若需要，如何实现？
看情况，
因为Stack<E extends Comparable<E>>，也就是E是实现Comparable接口的子类，所以要重写compareTo方法
如
class A implements Comparable<A> {
    public int compareTo(A a) {}
}
class B extends A implements Comparable<B> {
    pubnlic int compareTo(B b) {}
}
Stack<A> sa = new StackImpl<A>();
Stack<B> sb = new StackImpl<B>();2.最大最小还有中间值，有什么优一些的算法？（尤其中间值）
可以采用java自带的集合排序方法，关键就看你的Stack内部采用什么样的数据结构来保存数据
如果是用List，如
class StackImpl implements Stack<E extends Compatable<E>> {
    List<E> list = new LinkedList<E>(); //内部用List来保存数据    //找到栈中第size/2+1小的值，但不删除此数据
    public E peekMedian() {
        List<E> l = new ArrayList<E>(list);
        Collections.sort(l); //用集合排序
         return l.size() > 1 ? l.get(l.size()/2+1) : (l.size() > 0 ? l.get(0) : null);
    }
    
    
    //找到栈中最大值，但不删除此数据
    public E peekMaximum() {
        List<E> l = new ArrayList<E>(list);
        Collections.sort(l); //用集合排序
         return l.size() > 0 ? l.get(0) : null;
    }
    
    
    //找到栈中最小值，但不删除此数据
    public E peekMinimum() {
        List<E> l = new ArrayList<E>(list);
        Collections.sort(l); //用集合排序
         return l.size() > 0 ? l.get(l.size()-1) : null;
    }}

Answer 3

记得JDK 里面的stack 是用 List来实现的。

Answer 4

ArrayList  还是LinkedList呢？

Answer 5

class Stack1{
private Object[] elementData;
private int currentCapacity;
private int base;
private int top;
private int capacityIncrements;
private int initCapacity;

public Stack1(){
base = 0;
top = 0;
initCapacity = 10;
capacityIncrements = 10;
currentCapacity = initCapacity;
elementData = new Object[initCapacity];
}

public void push(Object obj) {
if (top < currentCapacity) {
elementData[top++] = obj;
}
else {
//扩容
currentCapacity += capacityIncrements; 
ensureCapacityHelper();
elementData[top++] = obj;
}
} private void ensureCapacityHelper() {
elementData = Arrays.copyOf(elementData, currentCapacity);
}
public int getSize() {
return top;
}

public Object pop() throws Exception {
if (top > base) {
Object obj = elementData[top - 1];
elementData[top--] = null;
return obj;
} else {
throw new ArrayIndexOutOfBoundsException("stack is null");
}
}


public String toString() {
String str = "";
for (int i = 0; i < top; i ++) {
str += elementData[i].toString() + " ";
}
return str;
}


public Object getTop() {
return elementData[top - 1];
}
}

Answer 6

Stack 用 Vector  实现的   都是遗留类
现在的是LinkedList 实现的

Answer 7

public class Stack<E extends Comparable<E>> {
  private LinkedList<E> storage = new LinkedList<E>();
  public void push(E v) { storage.addFirst(v); }
  public E peek() { return storage.getFirst(); }
  public E pop() { return storage.removeFirst(); }
  public boolean empty() { return storage.isEmpty(); }
  public String toString() { return storage.toString(); }
  public E peekMedian(){
    //这个操作就有危险了，首先如果栈为空，后果不堪设想
      //还有需要算重复吗，比如 1,2 ，2 ，3 。  2 
      //第三大的元素究竟2还是3，如果是2，那么第二大呢 也是2？？,（比较的时候他们可是同等地位）      
      //Set<E> set =  new  TreeSet<E>( storage);//。
       return null;
  }  
  public E peekMaximum(){//找到栈中最大值，但不删除此数据
      E temp = storage.get(0);;
      for(int i=1; i<size(); i++)  
  if(temp.compareTo(storage.get(i))==-1) temp = storage.get(i);
      return temp;
  }
  public E peekMinimum(){//找到栈中最小值，但不删除此数据
      E temp = storage.get(0);;
      for(int i=1; i<size(); i++)  
  if(temp.compareTo(storage.get(i))==1) temp = storage.get(i);
      return temp;
  }
  public int size(){return storage.size();};//返回栈的长度
} ///:~
class E implements Comparator<E>{
    public int compare(E o1, E o2) {
return 0;//return 1; return -1;
    }  
}