Stuck on a stack, can't pop!
I need to generate random numbers (I am a second semester "programer" I use the title loosely) and I need to push numbers onto two stacks.
the first two numbers I place, first one on left stack, second on right stack. Ok, now as the numbers come off, I compare them,but first I check things. Perhaps I will put my code here and you will see.
class SlinkySort
{
public static void display(StackX s1, int max)
{
StackX s2 = new StackX(max);
int y;
while(!s1.isEmpty())
{
y = s1.pop();
System.out.println(y);
s2.push(y);
}
while (!s2.isEmpty())
{
y = s2.pop();
s1.push(y);
}
}
public static void main(String[] args)
{
int i;
int rX =0;//Random x value
StackX leftStack = new StackX(10);
StackX rightStack = new StackX(10);
for(i=0; i<10; i++)
{
rX = (int)(100*Math.random()+1);
System.out.println(rX);
if(leftStack.isEmpty())
leftStack.push(rX);
else if (rightStack.isEmpty())
rightStack.push(rX);
else if(!leftStack.isEmpty())
{
int w =leftStack.peek();
int x = rightStack.peek();
while(rX < w )
{
leftStack.pop();
rightStack.push(w);
}
leftStack.push(rX);
while (rX > x)
{
x = rightStack.pop();
leftStack.push(x);
}
rightStack.push(rX);
if (rX < x)
{
//x = rightStack.pop();
//leftStack.push(x);
rightStack.push(rX);
}
}
}
leftStack.print();
rightStack.print();
}
}
So, I get an error when I try to pull the first element off the stack, thus leaving the stack empty. Keep in mind I have not been taught nodes, or any pointers yet, so i am not allowed to incorporate them.
I need this to work in Static classes, but have decided to get it to sort in the main, then figure the logistics of moving it.
Any advice (and no flames) would be welcome.
[2050 byte] By [
yeti_a] at [2007-10-2 0:55:27]
Well, what's the error? The first thing you have to use is to pay attention to the error messages and use their valuable information to solve the problems. It seems like a common newbie mistake is to interpret error messages as just some kind scolding, and that the proper response is to feel chastized but not to do anything about it.
Also when you post code, please wrap it in [code][/code] tags so it's legible.
Sorry, I should have previewed the post first.
Ok, error message is as follows (from Eclipse)
java.lang.ArrayIndexOutOfBoundsException
at problemset1Package.StackX.pop(StackX.java:34)
70
29
99
at problemset1Package.SlinkySort.main(SlinkySort.java:58)
Exception in thread "main"
I suspect that it is out of bounds because I am trying to remove the only item, but to me that doesnt make sense, when I do my print at the end, I will transfer to the right stack and print from there so the numbers are smallest to largest, but I think that is what the out of bounds is
yeti_a at 2007-7-15 18:15:23 >
Perhaps I should show the class that is called to....
public class StackX {
private int maxSize;// size of stack array
private int[] stackArray;
private int top;// top of stack
//--
public StackX(int s) // constructor
{
maxSize = s; // set array size
stackArray = new int[maxSize]; // create array
top = -1;// no items yet
}
//--
public void push(int j)// put item on top of stack
{
stackArray[++top] = j;// increment top, insert item
}
//--
public int pop()// take item from top of stack
{
return stackArray[top--]; // access item, decrement top
}
//--
public void print()//prints with an instance method
{
System.out.println("Display from instance method");
for (int i = top; i >-1; i--)
System.out.println(stackArray[i]);
}
//--
public int peek() // peek at top of stack
{
return stackArray[top];
}
//--
public boolean isEmpty()// true if stack is empty
{
return (top == -1);
}
//--
public boolean isFull()// true if stack is full
{
return (top == maxSize-1);
}
//--
} // end class StackX
////////////////////////////////////////////////////////////////
yeti_a at 2007-7-15 18:15:23 >
No it seems that you're getting the ArrayIndexOutOfBoundsException because you're trying to remove an element when there aren't any elements left.Are you sure that you always call isEmpty before you pop?
Well, as I see it, and correct me if I am wrong, if the 1st 3 random numbers are 99, 88 and 3, and I am pushing the first to the left, the second to the right and then comparing, at some point one of those stacks will have to be empty for a second in order to place ( in this example) 3 on the left stack. I took my isEmpty call out because I didnt see how I would get a 99 off the bottom of the stack if it were the first number.
Does that make sense?
yeti_a at 2007-7-15 18:15:23 >
I don't understand what you're describing re: how you use the stacks, but in general I'd advise against taking the isEmpty out. Apparently it is trying to pop an empty stack, and it would be helpful in debugging your algorithm to see why.
Hmmm, let me see.
I have 2 stacks. the leftone I want to sort the numbers from lowest at the bottom to highest at the top, at the same time I want to take large numbers and place them on the right stack, which when I finish will go from largest (bottom) to smallest (top) of the right stack. My problem seems to lie with trying to pull a number (the first number placed onto the stack, either right or left) off of it in order to place a larger or smaller number beneath it, as the case may be.
Make sense?
yeti_a at 2007-7-15 18:15:23 >
Well, fine, but:
1) the problem isn't with popping, the problem is with popping when there's nothing to pop
2) so the bug isn't in your stack code, it's in the code that uses the stack
3) and you didn't post any of that code.
4) and the way to debug it is to put in some tracing statements to see at what point you're trying to pop an empty stack.
I'm sorry, you did post it, but without formatting.How about adding the tracing statements, and if you don't immediately see the problem (you probably will) post the sorting code, but formatted this time.
everything in the package is there. I have listed two classes. The StackX class worked ok for another application and is from the textbook. I'll keep reading and drinking coffee and maybe something will make sense
yeti_a at 2007-7-15 18:15:23 >
I inserted a display after the first two inserts at the top.
for(i=0; i<10; i++)
{
rX = (int)(100*Math.random()+1);
System.out.println(rX);
if(leftStack.isEmpty())
{leftStack.push(rX);
leftStack.print();
}
else if (rightStack.isEmpty())
{rightStack.push(rX);
rightStack.print();
}
and I get this to print out.:
77
Display from instance method
77
7
Display from instance method
7
89
java.lang.ArrayIndexOutOfBoundsException
at problemset1Package.StackX.pop(StackX.java:34)
at problemset1Package.SlinkySort.main(SlinkySort.java:62)
Exception in thread "main"
So, doesn't that show me that it is infact inserting into the stacks? So is it trying to pop from an empty stack? I mean it says that isEmpty is true of top = -1, and to me that doesnt seem to be the case.
yeti_a at 2007-7-15 18:15:23 >
Well, I suspect that you're popping from the stack more often than you're pushing.
I suspect the problem may be around here:
int w =leftStack.peek();
int x = rightStack.peek();
while(rX < w ) {
leftStack.pop();
rightStack.push(w);
}
leftStack.push(rX);
rX and w aren't going to change in those loops, but you keep popping that leftStack (and pushing w onto rightStack, potentially introducing extra incorrect data).
I suspect that you'd just end up popping that stack until you get the ArrayOutOfBoundsException.
Shouldn't you be grabbing the value that's popped and using it?
Anyway, even if you don't believe this is the problem, I'd suggest putting your debug statements around here to confirm what's going on.
yea, that would make sense, as it stays in that loop with the first peek value. Midnight, guess i'll try to rework it.
It is times like this I question why I went from a Computer Information major to a computer science, makes me question if I can do it, though this is my 2nd semester of programing ever, so maybe I am too hard on myself and should just ask for help sooner
yeti_a at 2007-7-15 18:15:23 >
Don't be hard on yourself; it's easy to make mistakes like this even if you have a lot of experience.In time you'll get better at anticipating where the mistakes are likely to be.
Thanks, well I am sure you will see more of me in the future, you were very helpful. thank you for your time.Yeti_
yeti_a at 2007-7-20 14:36:30 >
