• Post Reply Bookmark Topic Watch Topic
  • New Topic

Array based implementation of a stack - generic array creation & clear() issues  RSS feed

 
W Wilson
Greenhorn
Posts: 26
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Hiyo. So I have this stack. I'm writing out all the operations and what not but I'm having trouble bypassing this "generic array creation" problem. I'm meant to be creating an array based implementation of a stack and from my research from google and my various attempts at things, I have not found a solution that works.

In addition; I have all the operations written that I need except for one final one. And that is clear(). clear() is meant to empty the array, essentially it is a popAll() method. Then all I need to do is set up so I can print out the arrays and I should be able to handle everything else. That being said, can anyone point me in the right direction?

StackInterface:



ArrayStackWilson

 
Campbell Ritchie
Marshal
Posts: 56525
172
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
You are actually on the right lines.
You do not need a size variable and a top variable. They both measure the same thing on a stack because you always look at the top element. You only need one. If you use top you can simply return top + 1 from the size method. By the way, call it size() not getLength().

I suggest you go through the logic for push. Forget about pop and peek for the time being. Do one thing at a time and you can sort pop and peek later. Let's imagine that you already have 20 elements on the stack and you want to push one more element. Let's imagine that you have sufficient capacity. Write down the values of:-
  • top before the beginning of the method.
  • size before the beginning of the method
  • The contents of the square brackets [] in line 26 (= ++top).
  • the value of size at the end of the method.
  • the value of top at the end of the method.
  • Draw a diagram of the stack before the beginning of the method like this:-You can amend that diagram to show the state of the stack as you go through the push method, and the other methods.

    If you have satisfied yourself that push() is working correctly, you can consider the peek method. Do the same for pop

    Beware: you can write pop in such a manner as to create a memory leak. Your pop method will not compile because you have code after a return.
     
    Campbell Ritchie
    Marshal
    Posts: 56525
    172
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    Also decide what to do in push if you reach the capacity of the stack. You have two choices:-
  • 1: Copy the entire contents of the array into a larger array.
  • 2: Throw an Exception. I thought there was a ready made full stack exception but there isn't. Write one extending RuntimeException or one of its subclasses. Don&apso;t simply let it throw array index out of bounds exception.
  • You will have to consider what to do if you are popping or peeking a completely empty stack, too. You might throw one of these.
     
    Prasanna Raman
    Ranch Hand
    Posts: 410
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    Campbell Ritchie wrote:Write one extending RuntimeException or one of its subclasses.
    Campbell, I want to understand why you've said RuntimeException. Is this because the only way this exception can be encountered is through a flaw in the client code? Do we use RuntimeExceptions in such scenarios?

    I am always slightly confused about which one to extend.
     
    Junilu Lacar
    Sheriff
    Posts: 11476
    180
    Android Debian Eclipse IDE IntelliJ IDE Java Linux Mac Spring Ubuntu
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    My simple Rule of Thumb is to throw a RuntimeException if it's something that the programmer should not be doing.

    For example, if the API docs of the class specifies that "you should not call pop() if the stack is empty" then I would expect a RuntimeException to be thrown if a call is made to pop() when the stack is empty. If the programmer is testing his code properly, then he should see the exception getting thrown and he can make the appropriate code changes to check for isEmpty() before making the call to pop(). On the other hand, you could design your stack to be more forgiving and just return null when you try to pop() an empty stack. I'm sure there will be those who will argue for going one way or the other.
     
    Campbell Ritchie
    Marshal
    Posts: 56525
    172
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    I woiuld suggest that returning null is worse than throwing an unchecked exception. Remember that null might be a valid element on the stack.
     
    W Wilson
    Greenhorn
    Posts: 26
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    Right. Made some changes. Now, I just gotta figure out a way to print out all of the elements in a stack (preferred on the same line) and I should be good. Any ideas?

     
    Junilu Lacar
    Sheriff
    Posts: 11476
    180
    Android Debian Eclipse IDE IntelliJ IDE Java Linux Mac Spring Ubuntu
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    Campbell Ritchie wrote:I woiuld suggest that returning null is worse than throwing an unchecked exception. Remember that null might be a valid element on the stack.

    Not all stacks are designed equally. The java.util.Stack has the semantics you mention but that's not the be-all and end-all of stack design and semantics. There are stack designs where pop() returns void and you have to use top() to get a reference to the top element. You could design a stack that doesn't accept null elements, so a pop() that returns null is not all that bad vs throwing an exception. It all depends.

    In this case, however, given the OP's requirements, I agree that throwing an EmptyStackException would be the right thing to do.

    I don't see a need for the stackESize variable. It's just one more thing to track and an additional potential source of bugs. I would just calculate it as getLength() -> top + 1.
     
    Winston Gutkowski
    Bartender
    Posts: 10575
    66
    Eclipse IDE Hibernate Ubuntu
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    W Wilson wrote:Right. Made some changes. Now, I just gotta figure out a way to print out all of the elements in a stack (preferred on the same line) and I should be good. Any ideas?

    Yes. have a look at Arrays.toString(). You might have to copy the contents to an array of the right length first, but Arrays (java.util.Arrays) also has methods for doing that.

    As Campbell says, your implementation is certainly along the right lines - and it's nice and simple (which is always a good place to start). but here's a couple of things to consider:

    1. What if you push the n+1th element for a Stack of size n? The method will certainly throw an Exception, but what if someone calls that method from a try...catch block? In theory, they could simply log the error and then call the method again - and in that case, what would the value of top be?
    The simple answer is: I'm not sure; but I suspect it means that top could exceed stackArray.length.

    2. Same question with pop(): What if it's called several times in succession when the stack is empty? I suspect that means that top could end up being less than -1. And for that reason alone, it might be better to implement isEmpty() as:
    return top < 0;

    HIH

    Winston
     
    Campbell Ritchie
    Marshal
    Posts: 56525
    172
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    Winston Gutkowski wrote: . . .

    1. What if you push the n+1th element for a Stack of size n? The method will certainly throw an Exception, but what if someone calls that method from a try...catch block? In theory, they could simply log the error and then call the method again - and in that case, what would the value of top be? . . .
    The exception is thrown in the push method's first line. Surely when the Exception is created, the program state is wound back to what it was before. So there will be no risk of top exceeding the size of the stack. Similarly for empty stacks top cannot be less than −1.
     
    • Post Reply Bookmark Topic Watch Topic
    • New Topic
    Boost this thread!