使用双链表进行堆栈

Question

嘿。我被分配使用双链表做堆栈，我遇到了一个问题。我无法链接到前一个元素（虽然使用一个链接没有任何问题）。

class Node
{
    Data data;
    Node previous;
    Node next;
}

class Data
{
    int     size;
    double  price;
    boolean isOnOffer;
    char    sex;
    String  brand;

    Data(int size, double price, boolean isOnOffer, char sex, String brand){
        this.size       = size;
        this.price      = price;
        this.isOnOffer  = isOnOffer;
        this.sex        = sex;
        this.brand      = brand;
    }
}

class Stack
{
    private static int sizeOfStack;
    private static Node topElement;

    public static boolean isEmpty() { return topElement == null; }

    public static void Initialize() {
        sizeOfStack = 0; 
        topElement = null; 
    }

    public static void Push(Data x) {

        Node oldElement = topElement;
        topElement = new Node();
        topElement.data = x;
        topElement.next = oldElement;
        topElement.previous = null;
        //oldElement.previous = topElement; // <----- problem here

        sizeOfStack++;
    }

    public static void Pop() {
        if (!isEmpty()){
            topElement = topElement.next;   // delete first node
            sizeOfStack--;
        }
    }

    public static void Top() {
        int size =           topElement.data.size;
        double price =       topElement.data.price;
        boolean isOnOffer =  topElement.data.isOnOffer;
        char sex =           topElement.data.sex;
        String brand =       topElement.data.brand;
        System.out.println(size + " " + price + " " + isOnOffer + " " + sex + " " + brand);
    }

    public static void Kill() { }
    public static void Print() { }


    public static void main(String[] args){

        Push(new Data(37, 155, false, 'F', "Nike"));
        Push(new Data(38, 140, true, 'F', "Reebok"));
        Push(new Data(35, 160.99, false, 'F', "Converse"));
        Push(new Data(35, 20.99, true, 'F', "Inkaras"));
        Pop();
        Pop();

        Top();
    }

}

Answer 1

//oldElement.previous = topElement; // <----- 这里有问题

正如已经指出的：如果 oldElement 为 null，您将得到一个 NullPointerException。之前检查是否为 null，例如 if(oldElement != null) { oldElement.previous = topElement; }。

另请注意，Top() 方法不适用于空堆栈，它会在第一行 topElement.data... 中抛出 NPE。

Answer 2

看看不同的情况：

{Stack} //Top of stack is the leftmost node

[Node(Next|Prev)]

Case: #1 “空栈情况”

{null}

Push:

[Node1(null|null)]

Case: #2 “正常情况”

{[Node1(null|null)]}

Push:

[Node2(Node1|null)]

Change:

[Node1(null|null)] -> [Node1(null|Node2)]

看 Case: #3 我们发现它与 case #2 类似，不需要实现

{[Node2(Node1|null)],[Node1(null|Node2)]}

Push:

[Node3(Node2|null)]

Change:

[Node2(Node1|null)] -> [Node2(Node1|Node3)]