使用链表实现堆栈

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

Answer 2

为什么不直接使用 Stack 实施已经存在了吗？

或者更好（因为它实际上是一个链表，速度快且线程安全）： LinkedBlockingDeque

Answer 3

如果您谈论的是单个链表（一个节点具有对下一个对象的引用，但没有对前一个对象的引用），那么该类将如下所示：

public class LinkedListStack {

    private LinkedListNode first = null;
    private LinkedListNode last = null;
    private int length = 0;

    public LinkedListStack() {}

    public LinkedListStack(LinkedListNode firstAndOnlyNode) {
        this.first = firstAndOnlyNode;
        this.last = firstAndOnlyNode;
        this.length++;
    }

    public int getLength() {
        return this.length;
    }

    public void addFirst(LinkedListNode aNode) {
        aNode.setNext(this.first);
        this.first = aNode;
    }

}

public class LinkedListNode {

    private Object content = null;
    private LinkedListNote next = null;

    public LinkedListNode(Object content) {
        this.content = content;
    }

    public void setNext(LinkedListNode next) {
        this.next = next;
    }

    public LinkedListNode getNext() {
        return this.next;
    }

    public void setContent(Object content) {
        this.content = content;
    }

    public Object getContent() {
        return this.content;
    }

}

当然，您需要编写其余方法的代码让它正常有效地工作，但你已经掌握了基础知识。
希望这有帮助！

Answer 4

使用 LinkedList 实现堆栈 - 此 StackLinkedList 类在内部维护 LinkedList 引用。

StackLinkedList的push方法内部调用linkedList的insertFirst()方法

public void push(int value){
    linkedList.insertFirst(value);
}

StackLinkedList的方法内部调用linkedList的deleteFirst()方法

public void pop() throws StackEmptyException {
    try{
        linkedList.deleteFirst();
    }catch(LinkedListEmptyException llee){
        throw new StackEmptyException();
    }
}

完整程序

/**
 *Exception to indicate that LinkedList is empty.
 */

class LinkedListEmptyException extends RuntimeException{
    public LinkedListEmptyException(){
        super();
    }
    
    public LinkedListEmptyException(String message){
        super(message);
    }  
}

/**
 *Exception to indicate that Stack is empty.
 */

class StackEmptyException extends RuntimeException {
 
    public StackEmptyException(){
        super();
    }

    public StackEmptyException(String message){
        super(message);
    }
}

/**
 *Node class, which holds data and contains next which points to next Node.
 */
class Node {
    public int data; // data in Node.
    public Node next; // points to next Node in list.

    /**
     * Constructor
     */
    public Node(int data){
        this.data = data;
    }

    /**
     * Display Node's data
     */
    public void displayNode() {
        System.out.print( data + " ");
    }
}


/**
 * LinkedList class
 */
class LinkedList {
    private Node first; // ref to first link on list

    /**
     * LinkedList constructor
     */
    public LinkedList(){
        first = null;
    }

    /**
     * Insert New Node at first position
     */
    public void insertFirst(int data) {
        Node newNode = new Node(data);  //Creation of New Node.
        newNode.next = first;   //newLink ---> old first
        first = newNode;    //first ---> newNode
    }

    /**
     * Deletes first Node
     */
    public Node deleteFirst()
    {
        if(first==null){    //means LinkedList in empty, throw exception.               
            throw new LinkedListEmptyException("LinkedList doesn't contain any Nodes.");
        }
        Node tempNode = first; // save reference to first Node in tempNode- so that we could return saved reference.
        first = first.next; // delete first Node (make first point to second node)
        return tempNode; // return tempNode (i.e. deleted Node)
    }

        
    /**
     * Display LinkedList
     */
    public void displayLinkedList() {
        Node tempDisplay = first; // start at the beginning of linkedList
        while (tempDisplay != null){ // Executes until we don't find end of list.
            tempDisplay.displayNode();
            tempDisplay = tempDisplay.next; // move to next Node
        }
        System.out.println();   
    }
}


/**
 * For implementing stack using using LinkedList- This StackLinkedList class internally maintains LinkedList reference.
 */

class StackLinkedList{

    LinkedList linkedList = new LinkedList(); // creation of Linked List

    /**
     * Push items in stack, it will put items on top of Stack.
     */
    public void push(int value){
        linkedList.insertFirst(value);
    }

    /**
     * Pop items in stack, it will remove items from top of Stack.
     */
    public void pop() throws StackEmptyException {
        try{
            linkedList.deleteFirst();
        }catch(LinkedListEmptyException llee){
            throw new StackEmptyException();
        }
    }

    /**
     * Display stack.
     */
    public void displayStack() {
        System.out.print("Displaying Stack >  Top to Bottom : ");
        linkedList.displayLinkedList();
    }
}


/**
 * Main class - To test LinkedList.
 */
public class StackLinkedListApp {
    public static void main(String[] args) {

        StackLinkedList stackLinkedList=new StackLinkedList();
        stackLinkedList.push(39);  //push node.
        stackLinkedList.push(71);  //push node.
        stackLinkedList.push(11);  //push node.
        stackLinkedList.push(76);  //push node.

        stackLinkedList.displayStack(); // display LinkedList
                    
        stackLinkedList.pop();  //pop Node
        stackLinkedList.pop();  //pop Node
        
        stackLinkedList.displayStack(); //Again display LinkedList
    }
}

OUTPUT

显示堆栈>从上到下：76 11 71 39

显示堆栈>从上到下：71 39

礼貌：http:// www.javamadesoeasy.com/2015/02/implement-stack-using-linked-list.html

Answer 5

使用 STL 适配器 std::stack。为什么？因为您不必编写的代码是完成任务的最快方法。 stack 经过充分测试，可能不需要您的任何关注。为什么不呢？因为您的代码需要一些特殊用途的要求，此处未记录。

默认情况下，stack使用deque双端队列，但它只需要底层容器支持“反向插入序列”，也称为.push_back.

typedef std::stack< myType, std::list<myType> > myStackOfTypes;

Answer 6

这是一个使用数组和链表堆栈实现的教程实现。

这取决于具体情况。

数组：- 你不能调整它的大小（固定大小）
LinkedList：- 它比基于数组的列表需要更多的内存，因为它想将下一个节点保留在内存中。

Answer 7

我看到很多使用 LinkedList 的堆栈实现，最后我明白了什么是堆栈..并自己实现了堆栈（对我来说它是干净且高效的）。我希望您欢迎新的实施。代码如下。

class Node
{
    int     data;
    Node    top;

    public Node()
    {

    }

    private Node(int data, Node top)
    {
        this.data = data;
        this.top = top;
    }

    public boolean isEmpty()
    {
        return (top == null);
    }

    public boolean push(int data)
    {
        top = new Node(data, top);
        return true;
    }

    public int pop()
    {
        if (top == null)
        {
            System.out.print("Stack underflow<-->");
            return -1;
        }
        int e = top.data;
        top = top.top;
        return e;
    }
}

这是它的主要类。

public class StackLinkedList
{
    public static void main(String[] args)
    {
        Node stack = new Node();
        System.out.println(stack.isEmpty());
        stack.push(10);
        stack.push(20);
        stack.push(30);
        System.out.println(stack.pop());
        System.out.println(stack.pop());
        System.out.println(stack.isEmpty());
        System.out.println(stack.pop());
        System.out.println(stack.isEmpty());
        System.out.println(stack.pop());

    }
}