A little analysis of stack from a example from “Thinking in Java”

Introduction

I’m reading “Thinking in Java (Forth Edition)” about Generics and find this example by a glance. But then I get interest of how exactly the stack works.

If any of my analysis is wrong or imprecise, please tell me.

Code

Actually the book I read is Chinese edition at page 357 of chapter 15. I guess it will not be considered as a infringement to the publisher if telling the reference.

public class LinkedStack<T> {
    private static class Node<U>{
        U item;
        Node<U> next;
        Node(){item = null; next = null;}
        Node(U item, Node<U> next){
            this.item = item;
            this.next = next;
        }
        boolean end(){ return item == null && next == null;}
    }
    private Node<T> top = new Node<>();
    public void push(T item){
        top = new Node<>(item, top);
    }
    public T pop(){
        T result = top.item;
        if(!top.end()){
            top = top.next;
        }
        return result;
    }
    public static void main(String[] args){
        LinkedStack<String> lss = new LinkedStack<>();
        for(String s : "Phasers on stun!".split(" "))
            lss.push(s);
        String s;
        while ((s=lss.pop())!=null)
            System.out.println(s);
    }
}
// The result is 
// stun!
// on
// Phasers

Analysis

Obviously, U is exactly the T, and a String in this example. That’s because of private Node<T> top = new Node<>(); and top = new Node<>(item, top);. Here’s all Generics knowledge in here.

Model

Let me use a diagram to show a instance of Node and LinkedStack. 

New stack

After you new the lss, you get a totally empty stack. The Pn point to the Node create by new Node<T>()

Push

Then let’s call void push(T item) twice, a is the first and b is the second. Notice the pa and pb is generated after calling new Node<T>(item,top).

Pop

And let’s call T pop() twice, to see how b and a walks out. Notice the lss is using next (pb in first pop(), pa in second pop()) to get the real Node.