使用鏈接列表實現堆棧

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

假設你真正想從頭做到這一點，而不是使用perfectly good existing stack implementations之一，那麼我會建議：

• 創建「MyStack < T>」
• 在MyStack創建一個「私有靜態最後一類節點< T>」內部類爲每個L1類，它實現你想要的任何界面（或許名單< T>？）清單項目。每個節點包含對T類型對象的引用和對「下一個」節點的引用。
• 向MyStack添加「topOfStack」節點引用。
• 推送和彈出操作只需要在此topOfStack節點上操作。如果它爲空，則堆棧爲空。我建議使用與標準Java堆棧相同的方法簽名和語義，以避免後來的混淆.....
• 最後實現您需要的任何其他方法。對於加分，以這樣的方式實現「可迭代< T>」它記住在沒有任何額外的存儲分配創建迭代器的瞬間堆棧不可改變狀態（這是可能 :-)）

Answer 2

使用STL適配器std::stack。爲什麼？因爲您不必編寫的代碼是完成任務的最快方式。 stack經過充分測試，可能不需要您的任何關注。爲什麼不？因爲你的代碼需要一些特殊用途的需求，這裏沒有記錄。

默認情況下stack使用deque雙端隊列，但它只需要底層容器支持「後退插入序列」，也稱爲.push_back。

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

Answer 3

爲什麼不只是使用Stack實現已經存在？

或者更好（因爲它真的是一個鏈表，它的速度更快，其線程安全）：LinkedBlockingDeque

Answer 4

如果你在談論一個單鏈表（一個節點到下一個對象的引用，而不是以前的一個），那麼類會是這個樣子：

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 5

這裏是一個教程，implements stack in Java using linked list。它實現push和pop方法以及迭代器來遍歷堆棧項。希望它會有所幫助。

Answer 6

用於使用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 7

這裏是使用數組和鏈接列表的教程實現stack implementation。

這取決於具體情況。

Array： - 您無法調整它的大小（修正大小） LinkedList： - 它比基於陣列的內存需要更多的內存，因爲它希望將下一個節點保留在內存中。

Answer 8

我看到很多使用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()); 

    } 
}