java - 使用链表实现堆栈

Question

在 Java 中使用链表实现堆栈的最佳方法是什么？

编辑:我会将最好定义为使用干净代码最有效。我已经使用数组来实现堆栈，但不熟悉链接列表，所以想知道是否有人可以帮助我实现类似于下面的东西:

public class StackArray{

    private Object [] objArray;
    private int stackSize;

    public StackArray(){
        objArray = new Object[50];
        stackSize = 0;
    }

    public StackArray(int size){
        objArray = new Object[size];
        stackSize = 0;
    }

    //public interface methods - push, pop, top, empty & clear
    public void push(Object o)throws StackArrayException{
        if(stackSize < objArray.length){
            objArray[stackSize] = o;
            stackSize ++;
        }else{
            throw new StackArrayException("Stack Overflow");
        }
    }

    public Object pop()throws StackArrayException{
        if(stackSize != 0){
            stackSize--;
            return(objArray[stackSize]);
        }else{
            throw new StackArrayException("Stack Underflow");
        }
    }

    public void top() throws StackArrayException{
        if(stackSize != 0){
            return(objArray[stackSize-1]);
        }else{
            throw new StackArrayException("Stack Underflow");
        }
    }

    public boolean empty(){
        return (stackSize == 0):
    }

    public void clear(){
        stackSize = 0;
    }
}

编辑:如果有人感兴趣，这里是链表实现..

public class StackList{
    private Node listHead;

    protected class Node{
    protected Object datum;
    protected Node next;

    public Node(Object o, Node n){
        datum = o;
        next = n;
    }

    public StackList(){
        listHead = null;
    }

    //public interface methods - push pop top empty clear
    public void push(Object o){
        listHead = new Node(o, listHead);
    }

    public Object pop() throws StackListException{
        if(listHead!=null){
            Object top = listHead.datum;
            listHead = listHead.next;
            return top;
        }else{
            throw new StackListException("Stack Underflow");
        }
    }

    public Object top()throws StackListException{
        if(listHead != null){
            return(listHead.datum);
        }else{
            throw new StackListException("Stack Underflow");
        }
    }

    public boolean empty(){
        return (listHead == null);
    }

    public void clear(){
        listHead = null;
    }
}

Answer 1

假设您真的想从头开始而不是使用 perfectly good existing stack implementations 中的一个那么我会推荐:

• 创建一个“MyStack< T >”类来实现您想要的任何接口(interface)(也许是 List < T >？)
• 在 MyStack 中为每个链表项创建一个“private static final class Node< T >”内部类。每个节点都包含对类型 T 对象的引用和对“下一个”节点的引用。
• 添加对 MyStack 的“topOfStack”节点引用。
• push 和pop 操作只需要在这个topOfStack 节点上操作即可。如果为 null，则 Stack 为空。我建议使用与标准 Java 堆栈相同的方法签名和语义，以避免以后混淆......
• 最后实现您需要的任何其他方法。对于加分项，实现“Iterable< T >”时要记住在创建迭代器时堆栈的不可变状态，而无需任何额外的存储分配(这是可能:-) )