使用链接列表实现堆栈 [英] 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>内部类。每个节点都包含对类型为T的对象的引用和对下一个节点的引用。


• 向MyStack添加topOfStack节点引用。


• 推送和弹出操作只需要在这个topOfStack节点上运行。如果为null，则堆栈为空。我建议使用与标准Java堆栈相同的方法签名和语义，以避免以后混淆.....


• 最后实现您需要的任何其他方法。对于奖励积分，实施Iterable< T>，以便在创建迭代器时记住堆栈的不可变状态，而无需任何额外的存储分配（此 可能:-) ）

• 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屋！