7
\$\begingroup\$

Here's my implementation of a Stack in Java, all feedback welcome.

import java.util.Iterator;

public class Stack<T> implements Iterable<T> {
    private Node head = null;
    private int size;

    @Override
    public Iterator<T> iterator() {
        return new StackIterator();
    }

    private class Node<T>{

        public Node(T data){
            this.data = data;
            this.next = null;
        }
        T data;
        Node next;
    }

    private class StackIterator implements Iterator<T>{

        private Node current = head;
        @Override
        public boolean hasNext() {
            return current != null;
        }

        @Override
        public T next() {
            T item = (T) current.data;
            current = current.next;
            return item;
        }
    }

    public Stack(){
        size = 0;
        head = null;
    }

    public boolean isEmpty(){
        return head == null;

    }

    public void push(T item){
        Node p = new Node(item);
        if(head == null){
            head = p;
            size++;
            return;
        }
        p.next = head;
        head = p;
        size++;

    }

    public T pop(){
        Node current = head;
        if(current.next == null){
            head = null;
        }else{
            try {

                head = head.next;
                size--;
            }catch (Exception e){
                System.out.println("Popping off an empty stack:" + e);
            }
        }

        return (T)current.data;
    }


    public void trace(){
        Node current = head;
        while(current != null){
            System.out.println(current.data);
            current = current.next;
        }
    }
}
\$\endgroup\$
7
\$\begingroup\$
}catch (Exception e){
    System.out.println("Popping off an empty stack:" + e);
}

Why? You should be able to know if your stack is empty before you even try to pop it. And in that case, any consumer of that Stack class is going to expect an exception to be thrown.

Actually, something's fishy about that catch block.

Stack<int> foo = new Stack<int>();
foo.pop();

What does that do? head is null, you've made sure... twice.

Once here:

private Node head = null;

And another here:

public Stack(){
    size = 0;
    head = null;
}

The constructor seems redundant.

Now, with head being null, foo.pop() will throw a rather surprising NPE, despite that try/catch block seemingly handling the "stack is empty!" case.

You should avoid having that NPE thrown, and instead throw an EmptyStackException, for which your consumer code will be thankful.

\$\endgroup\$
0
\$\begingroup\$

Beside the things already mentioned I recommmend to omit the Iterable interface. It distorts the semantic of a Stack and inflates the responsibilities. You also can already build an iterator-like construct with the methods exposed by the stack.

This should not hinder you to introduce a StackIterator passing the Stack to the constructor to provide an element that is usable in for-while-loops. The difference is really small but you clearly separate responsibilites.

Without Iterable interface:

while (!stack.isNotEmpty()) {stack.pop()};
for(T data: new StackIterator(stack)) {};

With Iterable interface:

while (iterator.hasNext()) {iterator.next()}
for(T data: stack) {};

Another thing is traversing your recursive data structure "Node". To underline the structure your algorithms should follow. But that primarily depends on the memory efficiency you need and tail call optimization is available. The trace-method can look like this:

public void trace() {
   trace(head);
}

private void trace(Node current){
    if (current != null) {
        System.out.println(current.data);
    } else {
        trace(current.next);
    }
}

Due to JAVA restrictions JAVA does not support tail call optimizations of recursive calls. So this is a choice for or against readability and for or against potential StackOverFlowExceptions when the amount of stack elements becomes very high.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.