的圓形單鏈表

Question

我試圖用Java實現的一個堆棧的圓形單鏈表作爲底層數據結構實現堆棧。我放置了循環鏈表的插入函數來替換堆棧的推入函數等等。我沒有任何錯誤，但是有麻煩顯示堆棧。如果任何人都能指出我如何展示堆棧或發生什麼問題的正確方向，我會非常感激！

這裏是我的堆棧類

public class Stack { 
private int maxSize; // size of stack array 
private long[] stackArray; 
private int top; // top of stack 

private Node current = null;   // reference to current node 
private int count = 0;    // # of nodes on list 
private long iData; 


public Stack(int s) // constructor 
{ 
    maxSize = s; // set array size 
    stackArray = new long[maxSize]; // create array 
    top = -1; // no items yet 
} 
public void push(long j) // put item on top of stack 
{ 
    Node n = new Node(j); 
    if(isEmpty()){ 
     current = n; 
    } 
    n.next = current; 
    current = n; 
    count++; 
} 
//-------------------------------------------------------------- 
public Node pop() // take item from top of stack 
{ 
    if(isEmpty()) { 
     return null; 
    } 
    else if(count == 1){ 
     current.next = null; 
     current = null; 
     count--; 
     return null; 
    }else{ 
     Node temp = current; 
     current = current.next; 
     temp.next = null; 
     temp = null; 
     count--; 
    } 
    return current; 
} 
//-------------------------------------------------------------- 
public Node peek(long key) // peek at top of stack 
{ 
    Node head = current; 
    while(head.iData != key){ 
     head = head.next; 
    } 
    return head; 
} 
//-------------------------------------------------------------- 
public boolean isEmpty() // true if stack is empty 
{ 
    return (count == 0); 
} 
//-------------------------------------------------------------- 
public boolean isFull() // true if stack is full 
{ 
    return (count == maxSize-1); 
} 
//-------------------------------------------------------------- 

這裏是我的構造函數的類

public class Node{ 
public long iData;   // data item (key) 
public Node next;   // next node in the list 

public Node(long id){  // constructor 
    iData = id;    // next automatically nulls 
} 

public void displayNode(){ 
    System.out.print(iData + " "); 
} 

public static void main(String[] args) { 
    Stack newlist = new Stack(3); 
    newlist.push(1); 
    newlist.push(2); 
    newlist.push(3); 
    newlist.push(4); 

    newlist.pop(); 
    newlist.pop(); 

    newlist.push(4); 

    newlist.pop(); 

    newlist.peek(1); 

    newlist.push(5); 

    while(!newlist.isEmpty()) // until it’s empty, 
    { // delete item from stack 
     Node value = newlist.pop(); 
     System.out.print(value); // display it 
     System.out.print(" "); 
    } // end while 
    System.out.println(""); 
} 


//newlist.displayList(); 

}

Answer 1

首先，在你的主要功能使用的是System.out.print功能打印的價值。這將顯示對象的類名稱表示，然後顯示「@」及其哈希碼。

替換以下行

System.out.print(value); // display it 
System.out.print(" "); 

與

value.displayNode(); 

其次，在pop方法，你正在返回null當count爲1。它應該返回的最後一個元素是出現在列表中。另外，在最後的else if子句中，您應該返回temp。用這個代替你的代碼。

public Node pop() // take item from top of stack 
{ 
    if (isEmpty()) { 
     return null; 
    } 
    Node temp = current; 
    if (count == 1) { 
     current = null; 
    } else { 
     current = current.next; 
    } 
    count--; 
    temp.next = null; 
    return temp; 
} 

Answer 2

您的實現的幾個注意事項：

1）stackArray成員似乎是從另一個基於陣列棧實現的後遺症。

2）是最大尺寸真的需要？如果是這樣，你不強制在推棧的大小限制（..）

3）你推（..）方法不留列表循環。您應該將循環關閉回新節點。

4）添加一個虛擬節點，可以保持鏈表圓形，無論堆棧大小。這可以讓你的推送（..）方法簡單

5）PEEK（）方法的合同是不明確（以及任何印刷目的，例如迭代）。通常，您希望peek方法返回堆棧頂部的值，而不必刪除它。另外，爲什麼你返回類型節點？這個類應該對調用者隱藏起來 - 這是一個內部的實現細節，而不是你想在API中公開的東西。

下面是一個另類的實現，同時支持的toString（）：

public class Stack { 
    private Node EOS; 
    private int count = 0; 

    public Stack() { 
    EOS = new Node(0); 
    EOS.next = EOS; 
    } 

    public void push(long j) { 
    Node newNode = new Node(j); 
    Node tmp = EOS.next; 
    EOS.next = newNode; 
    newNode.next = tmp; 
    count++; 
    } 

    public Long pop() { 
    if (isEmpty()) { 
     return null; 
    } else { 
     count--; 
     Node node = EOS.next; 
     EOS.next = node.next; 
     return node.iData; 
    } 
    } 

    public Long peek() { 
    if (isEmpty()) { 
     return null; 
    } else { 
     Node node = EOS.next; 
     return node.iData; 
    } 
    } 

    public boolean isEmpty() { 
    return (count == 0); 
    } 

    @Override 
    public String toString() { 
    StringBuilder sb = new StringBuilder(); 
    Node p = EOS.next; 
    while (p != EOS) { 
     sb.append(p).append("\n"); 
     p = p.next; 
    } 
    return sb.toString(); 
    } 

    private static class Node { 
    public long iData; 
    public Node next; 

    public Node(long id) { 
     iData = id; 
    } 

    @Override 
    public String toString() { 
     return "<" + iData + ">"; 
    } 
    } 
}