使用链接列表实现堆栈

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

假设您真的想从头开始执行此操作，而不是使用现有的完美堆栈实现之一，那么我建议：

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