Results 1 to 14 of 14
Thread: Small problem with Stacks
- 10-14-2009, 11:02 PM #1
Member
- Join Date
- Sep 2009
- Posts
- 80
- Rep Power
- 0
Small problem with Stacks
Ok, I have a program that takes 2 stacks and sees whether they are equal in size and their elements are the same at the corresponding positions. Everything compiles right, the program runs, however no matter what I put in for either stack they are always coming out equal to each other and I'm just not seeing where It's going wrong. I bolded the code for the equalStack.
Here's the class :
Java Code:public class StackClass { private int maxStackSize; //variable to store the maximum //stack size private int stackTop; //variable to point to the top //of the stack private DataElement[] list; //array of reference variables //default constructor //Create an array of size 100 to implement the stack. //Postcondition: The variable list contains the base // address of the array, stackTop = 0, and // maxStackSize = 100. public StackClass() { maxStackSize = 100; stackTop = 0; //set stackTop to 0 list = new DataElement[maxStackSize]; //create the array }//end default constructor //constructor with a parameter //Create an array of size stackSize to implement the stack. //Postcondition: The variable list contains the base // address of the array, stackTop = 0, and // maxStackSize = stackSize. public StackClass(int stackSize) { if(stackSize <= 0) { System.err.println("The size of the array to implement " + "the stack must be positive."); System.err.println("Creating an array of size 100."); maxStackSize = 100; } else maxStackSize = stackSize; //set the stack size to //the value specified by //the parameter stackSize stackTop = 0; //set stackTop to 0 list = new DataElement[maxStackSize]; //create the array }//end constructor //Method to initialize the stack to an empty state. //Postcondition: stackTop = 0 public void initializeStack() { for(int i = 0; i < stackTop; i++) list[i] = null; stackTop = 0; }//end initializeStack //Method to determine whether the stack is empty. //Postcondition: Returns true if the stack is empty; // otherwise, returns false. public boolean isEmptyStack() { return (stackTop == 0); }//end isEmptyStack //Method to determine whether the stack is full. //Postcondition: Returns true if the stack is full; // otherwise, returns false. public boolean isFullStack() { return (stackTop == maxStackSize); }//end isFullStack //Method to add newItem to the stack. //Precondition: The stack exists and is not full. //Postcondition: The stack is changed and newItem // is added to the top of stack. // If the stack is full, the method throws // StackOverflowException public void push(DataElement newItem) throws StackOverflowException { if(isFullStack()) throw new StackOverflowException(); list[stackTop] = newItem.getCopy(); //add newItem at the //top of the stack stackTop++; //increment stackTop }//end push //Method to return the top element of the stack. //Precondition: The stack exists and is not empty. //Postcondition: If the stack is empty, the method throws // StackUnderflowException; otherwise, a // reference to a copy of the top element // of the stack is returned. public DataElement top() throws StackUnderflowException { if(isEmptyStack()) throw new StackUnderflowException(); DataElement temp = list[stackTop - 1].getCopy(); return temp; }//end top //Method to remove the top element of the stack. //Precondition: The stack exists and is not empty. //Postcondition: The stack is changed and the top // element is removed from the stack. // If the stack is empty, the method throws // StackUnderflowException public void pop() throws StackUnderflowException { if(isEmptyStack()) throw new StackUnderflowException(); stackTop--; //decrement stackTop list[stackTop] = null; }//end pop //Method to make a copy of otherStack. //This method is used only to implement the methods //copyStack and copy constructor //Postcondition: A copy of otherStack is created and // assigned to this stack. private void copy(StackClass otherStack) { list = null; System.gc(); maxStackSize = otherStack.maxStackSize; stackTop = otherStack.stackTop; list = new DataElement[maxStackSize]; //copy otherStack into this stack for(int i = 0; i < stackTop; i++) list[i] = otherStack.list[i].getCopy(); }//end copy //copy constructor public StackClass(StackClass otherStack) { copy(otherStack); }//end constructor //Method to make a copy of otherStack. //Postcondition: A copy of otherStack is created and // assigned to this stack. public void copyStack(StackClass otherStack) { if(this != otherStack) //avoid self-copy copy(otherStack); }//end copyStack [B]public boolean equalStack(StackClass otherStack) { if (this.isEmptyStack() == otherStack.isEmptyStack()) { try { while(top().compareTo(otherStack.top())==0) { pop(); otherStack.pop(); } return false ; } catch (StackUnderflowException e) { return true; } } else return false; }[/B] }
Java Code:import java.util.*; public class TestStack { public static void main(String[] args) { StackClass stack1 = new StackClass(); StackClass stack2 = new StackClass(); try { stack1.push(new IntElement(4)); stack1.push(new IntElement(5)); stack1.push(new IntElement(1)); stack1.push(new IntElement(3)); stack1.push(new IntElement(2)); } catch(StackOverflowException sofe) { System.out.println(sofe.toString()); System.exit(0); } stack1.copyStack(stack1); System.out.print("Stack 1 is: "); while (!stack1.isEmptyStack()) { System.out.print(stack1.top() + " "); stack1.pop(); } System.out.println(); try { stack2.push(new IntElement(1)); stack2.push(new IntElement(3)); stack2.push(new IntElement(2)); stack2.push(new IntElement(5)); stack2.push(new IntElement(4)); stack2.push(new IntElement(6)); stack2.push(new IntElement(7)); } catch(StackOverflowException sofe) { System.out.println(sofe.toString()); System.exit(0); } stack2.copyStack(stack2); System.out.print("Stack 2 is: "); while (!stack2.isEmptyStack()) { System.out.print(stack2.top() + " "); stack2.pop(); } System.out.println(); if(stack1.equalStack(stack2)) System.out.println("The two stacks are the same"); else System.out.println("The two stacks are not the same"); } }
- 10-14-2009, 11:15 PM #2
Senior Member
- Join Date
- Aug 2009
- Posts
- 2,388
- Rep Power
- 14
Your method in bold is very strange and doesn't do what you described.
For starters, what is a StackUnderflowException and why do you return true is one is caught?
Put some System.out.println statements to find out what is happening.
- 10-14-2009, 11:19 PM #3
Member
- Join Date
- Sep 2009
- Posts
- 80
- Rep Power
- 0
Ok, i threw System.out.println() in throughout the method and every time I run it it doesn't return anything at all, just a blank line, between the stack 1: stack2: and the if they are same statement.
- 10-14-2009, 11:25 PM #4
Senior Member
- Join Date
- Aug 2009
- Posts
- 2,388
- Rep Power
- 14
Put more printlns. The code wont just hang for no reason. You still didn't say what that StackUnderflowException is all about.
- 10-14-2009, 11:44 PM #5
Member
- Join Date
- Sep 2009
- Posts
- 80
- Rep Power
- 0
Ok, the stackunderflow is to catch the pop if the stack is empty by chance.
This is what I have for printlns and it gives me nothing in return, just a blank line.
Java Code:public boolean equalStack(StackClass otherStack) { if (this.isEmptyStack() == otherStack.isEmptyStack()) { try { while(top().compareTo(otherStack.top())==0) System.out.println(); { pop(); System.out.println(); otherStack.pop(); System.out.println(); } System.out.println(); return false ; } catch (StackUnderflowException e) { System.out.println(); return true; } } else System.out.println(); return false; }
- 10-15-2009, 12:15 AM #6
Member
- Join Date
- Sep 2009
- Posts
- 80
- Rep Power
- 0
Ok, I added a getSize() method to see what the stack sizes where coming back as.
Java Code:public int getSize() { return stackTop; }
I also switched around rewrote the equalStack method.
Java Code:public boolean equalStack(StackClass otherStack) { if (getSize() != otherStack.getSize()) { return false; } else { while(!isEmptyStack()) { if(top().compareTo(otherStack.top()) != 0) { return false; } else { pop(); otherStack.pop(); } } } return true; }
Here's the output:
Stack 1 is: 2 3 1 5 4
Stack 2 is: 7 6 4 5 2 3 1
Size of stack 1 is: 0
Size of stack 2 is: 0
The two stacks are the sameLast edited by SMHouston; 10-15-2009 at 12:18 AM.
- 10-15-2009, 12:51 AM #7
Member
- Join Date
- Sep 2009
- Posts
- 80
- Rep Power
- 0
Ok, now If I put the output line of the stack size WITHIN the code for the stacks it returns the correct size, but if i put it outside I get 0?
For Example:
Java Code:try { stack1.push(new IntElement(4)); stack1.push(new IntElement(5)); stack1.push(new IntElement(1)); stack1.push(new IntElement(3)); stack1.push(new IntElement(2)); stack1.getSize(); System.out.println(stack1.getSize()); <---- returns the correct size } \\Same code, anywhere outside of that block returns a size of 0
Last edited by SMHouston; 10-15-2009 at 12:55 AM.
- 10-15-2009, 01:06 AM #8
Member
- Join Date
- Sep 2009
- Posts
- 80
- Rep Power
- 0
Scratch that.
If I put it in the middle it always returns false no matter what I put in each stack, and if I put it after it always returns true no matter what I put in the stacks.
I "think" it has to do with the printing of the stacks, when it pop's it out, it empties both stacks and returns the size of 0, hence why it's not working. Any suggestions on how to fix this?Last edited by SMHouston; 10-15-2009 at 01:21 AM.
- 10-15-2009, 11:18 PM #9
Member
- Join Date
- Sep 2009
- Posts
- 80
- Rep Power
- 0
bump, still not understanding why its not comparing the size of each stack.
- 10-15-2009, 11:44 PM #10
Member
- Join Date
- Oct 2009
- Posts
- 63
- Rep Power
- 0
Could it have something to do with your initializeStack() method?
Java Code:public void initializeStack() { for(int i = 0; i < stackTop; i++) list[i] = null; stackTop = 0; }//end initializeStack
- 10-16-2009, 01:44 AM #11
Member
- Join Date
- Feb 2009
- Posts
- 92
- Rep Power
- 0
if (this.isEmptyStack() == otherStack.isEmptyStack())
I have to guess what you really want to do, but I'm guessing this isn't it. Ergo, I am answering a common programming error without having verified it.
You are comparing references, i.e. is the address of the object on the left side the same as the address on the right side.
Am assuming that you are trying to compare different stacks. Since they are not the same object, the conditional evaluates to false and you take the else branch, which does nothing except print a blank line, and return false. Suggest you need to change '==' to '!='.
Also, unless you are using the printlns simply as line feeds, put some messages in your println statements. Much easier to tell where "at 1" comes from than to tell one " " from " ". Most people would have trouble distinguishing the contents of one blank line from another.
- 10-16-2009, 01:53 AM #12
Member
- Join Date
- Sep 2009
- Posts
- 80
- Rep Power
- 0
I'm not sure where your referencing rdtindsm.
This is my equalStack method:
Java Code:public boolean equalStack(StackClass otherStack) { if (getSize() != otherStack.getSize()) { return false; } else { while(!isEmptyStack()) { if(top().compareTo(otherStack.top()) != 0) { return false; } else { pop(); otherStack.pop(); } } } return true; } }
I'm lost, not sure what is going on.
- 10-16-2009, 02:53 AM #13
Member
- Join Date
- Feb 2009
- Posts
- 92
- Rep Power
- 0
SMHouston:
I was referencing bold code in your original post. Sorry if I'm not reading your code closely enough to catch changes.
comments about the last code.
top lets you look at the top (first accessable element) on the stack.
The stack abstraction is generally pretty well understood and implemented in similar ways.
The standard operations are push, pop, and peek or top, and isEmpty. Java adds a method to locate a specific opject on a stack; this is not a method that would normally be a part of the stack interface.
Pop() REMOVES the item on the top of the stack. By repeatedly applying pop, you are confirming that the stack USED to contain the same items. When you are through, the stacks will still be identical, but empty. This is a little like Schroedingers cat: opening the box destroys the state.
From Dietel "Java for Programmers"
Because Stack extends Vector, all public Vector methods can be called on Stack objects, even if the methods do not represent conventional stack operations. For example, Vector method add can be used to insert an element anywhere in a stack—an operation that could "corrupt" the stack. When manipulating a Stack, only methods push and pop should be used to add elements to and remove elements from the Stack, respectively.
i.e. if you want to compare the contents without destroying, you will have to use vector methods.
get(index) and elementat(index) look like they would work.
- 10-16-2009, 03:34 AM #14
Member
- Join Date
- Sep 2009
- Posts
- 80
- Rep Power
- 0
Similar Threads
-
small problem
By barusk in forum NetworkingReplies: 4Last Post: 03-21-2009, 07:19 AM -
small problem in connection
By BsBs in forum CLDC and MIDPReplies: 1Last Post: 01-27-2009, 07:03 AM -
Small problem
By ayoood in forum New To JavaReplies: 2Last Post: 06-06-2008, 01:27 PM -
Stacks
By Zosden in forum Advanced JavaReplies: 15Last Post: 05-05-2008, 09:16 AM -
Using Stacks
By ravian in forum New To JavaReplies: 7Last Post: 11-28-2007, 10:53 AM
Bookmarks