LLStack.java

Download 
1/*2 * LLStack.java3 *4 * Computer Science S-22, Harvard University5 */6 7/*8 * A generic class that implements our Stack interface using a linked list.9 */10public class LLStack<T> implements Stack<T> {11    // Inner class for a node.  We use an inner class so that the LLStack12    // methods can access the instance variables of the nodes.13    private class Node {14        private T item;15        private Node next;16        17        private Node(T i, Node n) {18            item = i;19            next = n;20        }21    }22    23    // the field of the LLStack object24    private Node top;      // the node containing the top item25    26    /*27     * Constructs an LLStack object for a stack that is initially28     * empty.29     */30    public LLStack() {31        top = null;32    }33    34    /* 35     * isEmpty - returns true if the stack is empty, and false otherwise36     */37    public boolean isEmpty() {38        return (top == null);39    }40    41    /*42     * isFull - always returns false, because the linked list can43     * grow indefinitely and thus the stack is never full.44     */45    public boolean isFull() {46        return false;47    }48    49    /* 50     * push - adds the specified item to the top of the stack.51     * Always returns true, because the linked list is never full.52     */53    public boolean push(T item) {54        if (item == null) {55            throw new IllegalArgumentException();56        }57        58        // We insert the new node at the front of the linked list.59        // Note that we assign the new node's next field a reference to the60        // current front of the linked list (top).61        Node newNode = new Node(item, top);62        top = newNode;63        return true;64    }65    66    /* 67     * pop - removes the item at the top of the stack and returns a68     * reference to the removed object.  Returns null if the stack is69     * empty.70     */71    public T pop() {72        if (isEmpty()) {73            return null;74        }75        76        T removed = top.item;77        top = top.next;78        return removed;79    }80    81    /* 82     * peek - returns a reference to the item at the top of the stack83     * without removing it. Returns null is the stack is empty.84     */85    public T peek() {86        if (isEmpty()) {87            return null;88        }89        return top.item;90    }91    92    /*93     * toString - converts the stack into a String of the form 94     * {top, one-below-top, two-below-top, ...}95     */96    public String toString() {97        String str = "{";98        99        Node trav = top;100        while (trav != null) {101            str = str + trav.item;102            if (trav.next != null) {103                str = str + ", ";104            }105            trav = trav.next;106        }107        108        str = str + "}";109        return str;110    }111}