使用链表实现堆栈 [英] Implementing stack using linked lists

问题描述

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

What's the best way to implement a stack using linked lists in Java?

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

I would define best as most efficient using clean code. I have already used an array to implement a stack, but am not familiar with link lists so was wondering if anyone could help me implement something similar to below:

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;
    }
}

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

Here is the linked list implementation if anyone is interested..

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;
    }
}

推荐答案

假设您真的想从头开始执行此操作，而不是使用 完美的现有堆栈实现 那么我会推荐:

Assuming you genuinely want to do this from scratch rather than using one of the perfectly good existing stack implementations then I would recommend:

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

• Create a "MyStack< T >" class which implements any interfaces you want (perhaps List < T >?)
• Within MyStack create a "private static final class Node< T >" inner class for each linked list item. Each node contains a reference to an object of type T and a reference to a "next" Node.
• Add a "topOfStack" Node reference to MyStack.
• The push and pop operations just need to operate on this topOfStack Node. If it is null, the Stack is empty. I'd suggest using the same method signatures and semantics as the standard Java stack, to avoid later confusion.....
• Finally implement any other methods you need. For bonus points, implement "Iterable< T >" in such a way that it remembers the immutable state of the stack at the moment the iterator is created without any extra storage allocations (this is possible :-) )

这篇关于使用链表实现堆栈的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！