使用循环单向链表实现堆栈

Question

我正在尝试用一个循环的单向链表作为底层数据结构来实现Java中的a Stack。我将循环链表的insert函数替换为栈的push函数，依此类推。我没有任何错误，但我在显示堆栈时遇到了问题。如果有人能告诉我如何显示堆栈，或者哪里出了问题，我将不胜感激！

下面是我的堆栈类：

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方法中，当count为1时返回null。它应该返回列表中的最后一个元素。另外，在最后一个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)最大大小真的是要求吗？如果是这样，则不在push(..)中强制执行堆栈大小限制。

3)您的推送(..)方法不会使列表保持循环。您应该将循环闭合回新节点。

4)添加虚拟节点允许您保持链表循环，而不管堆栈大小。这可以使您的推送(..)方法更简单(以及用于打印目的的任何迭代)

5) peek()方法契约不明确。通常，您希望peek方法返回堆栈顶部的值，而不删除它。另外，为什么要返回类型Node？这个类应该对调用者隐藏-它是一个内部实现细节，而不是你想在你的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 + ">";
    }
  }
}