Results 1 to 14 of 14
  1. #1
    SMHouston is offline Member
    Join Date
    Sep 2009
    Posts
    80
    Rep Power
    0

    Default 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]
    }
    Here is my test program:

    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");
    		
    	}
    }

  2. #2
    r035198x is offline Senior Member
    Join Date
    Aug 2009
    Posts
    2,388
    Rep Power
    8

    Default

    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.

  3. #3
    SMHouston is offline Member
    Join Date
    Sep 2009
    Posts
    80
    Rep Power
    0

    Default

    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.

  4. #4
    r035198x is offline Senior Member
    Join Date
    Aug 2009
    Posts
    2,388
    Rep Power
    8

    Default

    Put more printlns. The code wont just hang for no reason. You still didn't say what that StackUnderflowException is all about.

  5. #5
    SMHouston is offline Member
    Join Date
    Sep 2009
    Posts
    80
    Rep Power
    0

    Default

    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;
    	}

  6. #6
    SMHouston is offline Member
    Join Date
    Sep 2009
    Posts
    80
    Rep Power
    0

    Default

    Ok, I added a getSize() method to see what the stack sizes where coming back as.

    Java Code:
    public int getSize()
    	 {
    	 	return stackTop;
    	 }
    Then put some printlns in the main program and both stacks are coming back with a size of 0.

    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;
    }
    Not sure why it's not returning a size at all, this could be my problem but I don't see it.

    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 same
    Last edited by SMHouston; 10-14-2009 at 11:18 PM.

  7. #7
    SMHouston is offline Member
    Join Date
    Sep 2009
    Posts
    80
    Rep Power
    0

    Default

    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-14-2009 at 11:55 PM.

  8. #8
    SMHouston is offline Member
    Join Date
    Sep 2009
    Posts
    80
    Rep Power
    0

    Default

    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 12:21 AM.

  9. #9
    SMHouston is offline Member
    Join Date
    Sep 2009
    Posts
    80
    Rep Power
    0

    Default

    bump, still not understanding why its not comparing the size of each stack.

  10. #10
    toymachiner62 is offline Member
    Join Date
    Oct 2009
    Posts
    63
    Rep Power
    0

    Default

    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
    you're always setting the stackTop = 0. That's not right is it?

  11. #11
    rdtindsm is offline Member
    Join Date
    Feb 2009
    Posts
    92
    Rep Power
    0

    Default

    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.

  12. #12
    SMHouston is offline Member
    Join Date
    Sep 2009
    Posts
    80
    Rep Power
    0

    Default

    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;
    	}
    }
    To answer toymachine, If I put the code to get size inside my code where I set the stacks, it returns the correct size of each stack, however once I leave that block of code, it has the stack size to 0.

    I'm lost, not sure what is going on.

  13. #13
    rdtindsm is offline Member
    Join Date
    Feb 2009
    Posts
    92
    Rep Power
    0

    Default

    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.

  14. #14
    SMHouston is offline Member
    Join Date
    Sep 2009
    Posts
    80
    Rep Power
    0

    Default

    Ok, thats what I was thinking, is it was removing all the items and thats why both were a size of 0 after the printout lines.

    I'll give this some work with the methods you suggested and see what I can come up with, thanks.

Similar Threads

  1. small problem
    By barusk in forum Networking
    Replies: 4
    Last Post: 03-21-2009, 06:19 AM
  2. small problem in connection
    By BsBs in forum CLDC and MIDP
    Replies: 1
    Last Post: 01-27-2009, 06:03 AM
  3. Small problem
    By ayoood in forum New To Java
    Replies: 2
    Last Post: 06-06-2008, 12:27 PM
  4. Stacks
    By Zosden in forum Advanced Java
    Replies: 15
    Last Post: 05-05-2008, 08:16 AM
  5. Using Stacks
    By ravian in forum New To Java
    Replies: 7
    Last Post: 11-28-2007, 09:53 AM

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •