使用链表实现堆栈

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 ”类，该类实现所需的任何接口（也许列出 ？）
• 在MyStack中，为每个链接列表项创建一个“私有静态最终类Node ”内部类。每个节点都包含对类型T对象的引用和对“下一个”节点的引用。
• 向MyStack添加“ topOfStack”节点引用。
• 推入和弹出操作仅需要在此topOfStack节点上进行。如果为空，则堆栈为空。我建议使用与标准Java堆栈相同的方法签名和语义，以避免以后造成混淆。
• 最后实现您需要的任何其他方法。奖励积分，以这样的方式实现“可迭代 ”它记住在没有任何额外的存储分配创建迭代器中的时刻堆栈的不可变的状态（这 是 可能的:-)）