2
\$\begingroup\$

Recently I was asked to implement a stack specifically for storing 'int' type data and find memory leaks. Isn't the garbage collector responsible for releasing all the memory? What are the possible memory leaks and how do I handle them?

import java.util.NoSuchElementException;
public class MyStack {

    private int stack[];
    private int top = -1;

    private MyStack() {

    }

    MyStack(int capacity) {
        stack = new int[capacity];
    }

    public void push(int data) {
        if(top == (stack.length-1))
            throw new IllegalStateException("Stack is full.");
        top++;
        stack[top] = data;
    }

    public int pop() {
        if(top == -1)
            throw new NoSuchElementException("Stack is empty.");
        int data = stack[top];
        top--;
        return data;
    }


    public int peek() {
        if(top == -1)
            throw new NoSuchElementException("Stack is empty.");
        return stack[top];
    }


    public int size() {
        return top + 1;
    }

    public boolean isEmpty() {
        if(top == -1)
            return true;
        return false;
    }

    public static void main(String args[]) {
        MyStack stack = new MyStack(5);
        stack.push(1);
        stack.push(2);
        stack.push(3);
        stack.push(4);
        stack.push(5);
        //stack.push(6);
        System.out.println("capacity::" + stack.size());
        System.out.println("top::" + stack.peek());
        System.out.println("pop::" + stack.pop());
        System.out.println("top::" + stack.peek());
        System.out.println("pop::" + stack.pop());
        System.out.println("pop::" + stack.pop());
        System.out.println("pop::" + stack.pop());
        System.out.println("pop::" + stack.pop());
        System.out.println("isEmpty::" + stack.isEmpty());
        //System.out.println(stack.pop());
    }
}
\$\endgroup\$
  • \$\begingroup\$ I assume size != 0 in peek() is a typo. \$\endgroup\$ – vnp Dec 11 '15 at 22:44
2
\$\begingroup\$
    private int stack[];

If you are only allowing this to be set in the constructor, you can make this final.

    private final int stack[];

Of course if you intend to resize it later, that won't work.

        if(top == (stack.length-1))
            throw new IllegalStateException("Stack is full.");

This pattern is fragile. If you change the code to support adding two or more items to the stack at the same time, this pattern fails.

        if (size() >= stack.length) {
            throw new IllegalStateException("Stack is full.");
        }

Switching to the range inequality rather than the single value inequality means that even if top has an invalid value, the expression returns the correct result. top >= stack.length - 1

Switching the 1 from the right to the left side gives a better parallel with other methods. top + 1 >= stack.length

Now we can see that we are essentially comparing the results of size() to the size of the stack array. So we might as well just do that, as it's clearer about what's happening. Translated literally there might be a slight performance drop, but it is more likely that this will get optimized out. And if it does get optimized out, it may actually allow a further optimization. You do a top++ immediately after the top + 1, so that good register management could eliminate the need for one or the other.

The C-style languages tend to have single statement and block versions of the same constructs. The problem that arises is that the single statement versions can be confusing to edit. Occasionally people try to add a second statement without converting it to the block form. This doesn't work but looks correct enough that it can be hard to diagnose. Always using the block version avoids that problem.

    public boolean isEmpty() {
        if(top == -1)
            return true;
        return false;
    }

This is more complicated than it needs to be.

    public boolean isEmpty() {
        return top == -1;
    }

If you are returning a boolean value, you don't need an if/else construct. It is sufficient to return the result directly.

Memory leaks in Java

The garbage collector can only free memory if it realizes that you are done with it. You can find more discussion of this at Creating a memory leak with Java

\$\endgroup\$
3
\$\begingroup\$

Memory leak

No, there's no memory leak in your program. If you changed the underlying data type from int to an object type, then you would have, loosely speaking, a memory leak in this method:

public int pop() {
    if(top == -1)
        throw new NoSuchElementException("Stack is empty.");
    int data = stack[top];
    top--;
    return data;
}

If stack was of type Object[], then the element you popped, would still be referenced. Even though it's no longer intended to be used, the popped element would stay referenced in there, until the array slot is overwritten. The remedy is simple, just null out the unused array slot:

public int pop() {
    if(top == -1)
        throw new NoSuchElementException("Stack is empty.");
    int data = stack[top];
    stack[top] = null;
    top--;
    return data;
}

This doesn't apply to your solution. There is nothing to "null out" (null is not a valid value for an int), there's nothing to be garbage collected.

And it would be a memory leak only loosely speaking. Due to the objects not garbage collected, you might experience reduced performance due to the increased memory footprint, and paging to disk (if you run out of memory).

Usability

You made the parameterless constructor private, and thus forbidden. At the minimum, you should add a comment to the constructor body to explain why it is forbidden.

And really, why is it forbidden? Users of this stack are forced to think about a suitable capacity, but very often there is no good way to anticipate the needed capacity, and then users will end up picking something arbitrary. Granted, anything that you pick will be arbitrary too, but at least you don't make your users think.

Supporting other types

Although your specs are asking to store int values, you could make your implementation work with any type, at negligible cost. So I urge you to do that. If the assignment requires a usage without type parameters, you could create a wrapper class that specializes on the desired type, for example:

class MyStack<T> {
    // ...
}

public class MyIntStack extends MyStack<Integer> {}

Another "cost" of course of the generalization is that you would have to watch out for memory leaks, and null out the popped element as explained earlier.

\$\endgroup\$
  • \$\begingroup\$ Thanks @mdfst13, you pointed out some things I completely overlooked. Fixed now, many thanks. \$\endgroup\$ – janos Dec 15 '15 at 14:16

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.