john February 2016

linked stack implementation

My problem here is with pop and size stack. I know that pop removes the top value and replaces it with the next value. How do I do that?

Also, what's the right way to get the size?

The code:

    public int pop()
    { 

          if (isEmpty())
            throw new RuntimeException("Pop attempted on an empty stack");
        else
        {
            return  m_top.value  ;  
        }

    }

    // return the size of the stack
    public int size()
    {       

          if (m_top == null)
        return 0;
        else
        return m_top.value; 
    }

Answers


zoom February 2016

A fine way to be able to retrieve the size of your stack at any moment is to maintain it internally.

As suggested by @Peter Lawrey in the comments, looking to real implementing in the JDK can be a great source of inspiration, even if it can be scary at the beginning. For example, you will see that the size method in LinkedList is implemented this way, an internal size property is maintained for each linked list instance.

For the pop method, you need to have a precise idea of how you will implements your stack. For pop you at least need to be able to retrieve the previous item from the item at the top of your stack. I see that you use a Node object internally, did you created this class? Is this a part of a homework? If you look closely to the linkedlist implementation again you will see that it also use a Node object (certainly not a coincidence...) that stores a reference to its next and previous object.


cricket_007 February 2016

I know that pop removes the top value and replaces it with the next value. How do I do that?

You need to reassign the m_top variable to it's link.

public int pop() {

    if (isEmpty())
        throw new RuntimeException("Pop attempted on an empty stack");
    else {
        int top_value = m_top.value;
        // Move the top off the "stack" by moving the pointer
        m_top = m_top.link;
        return top_value;
    }
}

way to get the size?

You count how many Nodes are in the list instead of returning the value of the top Node. As mentioned in the comments, though, this is not the "most efficient way".

public int size() {
    int size = 0;

    if (isEmpty())
        return size;
    else {
        Node tmp = m_top;

        do {
            size++;
            tmp = tmp.link;
        } while (tmp != null);
    }

    return size;
}

Post Status

Asked in February 2016
Viewed 1,492 times
Voted 9
Answered 2 times

Search




Leave an answer