?
Solved

Stack / Template Code Help

Posted on 2003-03-30
19
Medium Priority
?
284 Views
Last Modified: 2010-04-01
1. For the destructor. I am going to do a loop that pop's until empty, is this correct, and/or the best way to do the destructor?

2. How does the general code for the template look?  Also since this stack uses a template I cannot always return an integer for pop() if the stack is empty, and push() if the stack is full.  For explanation please look at the code below... also I want to keep push() as type void.

Thanks

---------------
stack.h
---------------
#ifndef STACK_H
#define STACK_H

template<class ItemType>

struct Node
{
  ItemType value;
  Node *next;
}

class Stack
{
 public:
  Stack();
  ~Stack();
  void push(ItemType);
  ItemType pop();
  bool isFull();
  bool isEmpty();

 private:
  Node *top;
};

#endif

------------
stack.cpp
------------
#include "stack.h"

template<class ItemType>

Stack::Stack()
{
  top=NULL;
}

Stack::~Stack();
{
  // destructor, no code yet
}

void Stack::push(ItemType item)
{
  if(!isFull())
    {
      Node*temp=new Node;
      temp->value=item;
      temp->next=top;
      top=temp;
    }
  else
    {
      return -1;
    }
}

ItemType Stack::pop()
{
  if(!isEmpty())
    {
      Node*temp=top;
      ItemType x=temp->value;
      top=top->next;
      delete temp;
      return x;
  else
    {
      return -1;
    }
}

bool Stack::isFull()
{
  Node*tester=new(nothrow) Node;
  if(tester==0)
    {
      return true;
    }
  else
    {
      delete tester;
      return false;
    }
}

bool Stack::isEmpty()
{
  return(top==NULL;)
}
0
Comment
Question by:killer455
[X]
Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

  • Help others & share knowledge
  • Earn cash & points
  • Learn & ask questions
  • 7
  • 5
  • 4
  • +2
19 Comments
 
LVL 15

Expert Comment

by:efn
ID: 8235966
1.  Your plan for the destructor is functionally correct and has the advantage of being simple.  A loop that just traversed the list and deleted the Nodes without doing anything with the values would be more efficient, but that may not matter.

2.  If you try to compile this, the compiler will inform you that you need to declare a lot more things as templates.  In the header file, Node is a template, but Stack is not, and ItemType is not defined within Stack.  Similarly, in the cpp file, only the constructor is a template.

As you know, the error-handling problems get worse when you convert this class to a template.  If you want pop to return -1 when the stack is empty, that will only work if there is a conversion from signed int to ItemType.  And push still can't return -1 if its return type is void.

There is also a possible problem with using .h and .cpp files as with non-template code.  With some compilers, this will work, but with others, the compiler needs to see the implementation code when it compiles the client code.  Common solutions are to put the implementation code in the .h file or have the .h file #include the .cpp file at the end.

--efn
0
 

Author Comment

by:killer455
ID: 8236209
How does this look?

---------------
stack.h
---------------
#ifndef STACK_H
#define STACK_H

#define LIST_IS_EMPTY 1
#define LIST_IS_EMPTY 1

template<class ItemType>
struct Node
{
 ItemType value;
 Node *next;
}

template<class ItemType>
class Stack
{
public:
 Stack();
 ~Stack();
 void push(ItemType);
 ItemType pop();
 bool isFull();
 bool isEmpty();

private:
 Node *top;
};

#endif

------------
stack.cpp
------------
#include "stack.h"

template<class ItemType>
Stack::Stack()
{
 top=NULL;
}

template<class ItemType>
Stack::~Stack();
{
 while(pop());
}

template<class ItemType>
void Stack::push(ItemType item)
{
 if(isFull()==false)
   {
     Node*temp=new Node;
     temp->value=item;
     temp->next=top;
     top=temp;
   }
 else
   {
     throw STACK_IS_FULL;
   }
}

template<class ItemType>
ItemType Stack::pop()
{
 if(isEmpty()==false)
   {
     Node*temp=top;
     ItemType x=temp->value;
     top=top->next;
     delete temp;
     return x;
 else
   {
     throw LIST_IS_EMPTY;
   }
}

template<class ItemType>
bool Stack::isFull()
{
 Node*tester=new(nothrow) Node;
 if(tester==0)
   {
     return true;
   }
 else
   {
     delete tester;
     return false;
   }
}

template<class ItemType>
bool Stack::isEmpty()
{
 return(top==NULL;)
}
0
 
LVL 6

Expert Comment

by:GaryFx
ID: 8236242
One way to deal with the problem of the return value for pop is to have two separate functions: top to return the top element, and pop to remove one element (but without returning its value).  That way, pop can return a bool indicating whether or not the stack was empty.  I don't remember whether it is Meyers or Sutter (or perhaps both) who recommend this, in their respective series ([More] (Effective|Exceptional) C++).

I don't believe your isFull is correct.  A new (nothrow), followed by a delete, doesn't guarantee that the next new will succeed (certainly not if it's multithreaded, but I doubt it in any case).

There are two ways to handle it.  One is to just use and test the nothrow version directly, i.e. with push:

Node *temp = new (nothrow) Node;
if (temp == 0) return -1;
...

The other is to simply let the exception propagate.

Note that your current push doesn't return a value when it succeeds.

Gary



0
VIDEO: THE CONCERTO CLOUD FOR HEALTHCARE

Modern healthcare requires a modern cloud. View this brief video to understand how the Concerto Cloud for Healthcare can help your organization.

 

Author Comment

by:killer455
ID: 8236412
Gary,

I'm not sure I understand this statement...

There are two ways to handle it.  One is to just use and test the nothrow version directly, i.e. with push:

Node *temp = new (nothrow) Node;
if (temp == 0) return -1;

Thanks

0
 
LVL 30

Expert Comment

by:Mayank S
ID: 8236544
>> if(isEmpty()==false)
>>   {
>>     Node*temp=top;
>     ItemType x=temp->value;
>>     top=top->next;
>>     delete temp;
>>     return x;       // ???? - WHERE'S THE CLOSING BRACE FOR THE if ()?
>> else
>>   {
>>     throw LIST_IS_EMPTY;
>>   }

Also:

>> return(top==NULL;) // the semi-colon is inside

return ( top == NULL ) ;


Mayank.
0
 

Author Comment

by:killer455
ID: 8236652
Hi mayank,

Thanks for the tips, I believed you helped me with some other problems.  What is your opinion with isFull() and what to return for pop() and push()??

Thanks

Ben
0
 
LVL 15

Expert Comment

by:efn
ID: 8236834
Just as a reference point, the stack class in the standard library has top and pop functions as Gary described.  Both have undefined behavior with an empty stack, putting the burden on the caller of avoiding this situation.  Presumably, if the push function can't allocate memory, it throws a bad_alloc exception.

Your push function calls isFull, which allocates a Node and then throws it away.  Assuming this works, push then allocates another Node itself.  Gary was suggesting that the push function just to try to allocate a Node itself, without calling isFull.  If the allocation succeeds, the function can use the Node; if the allocation fails, it can take whatever error action you decide on.  I agree that this would be simpler, more efficient, and more reliable.

--efn
0
 
LVL 30

Expert Comment

by:Mayank S
ID: 8236902
Hi Ben,

I agree with efn that the push () function can be modified so that it doesn't call isFull () at all, but simply allocates memory and then checks if the allocation was successful or not. In that case, you can also remove your isFull () function altogether. As for your isEmpty () and pop () functions, I don't think that there's anything to be modified there..

Mayank.
0
 

Author Comment

by:killer455
ID: 8237341
Ok.  

1. Is using throw the right way to handle an empty stack pop() though?

2. Also just out of curiosity, for isFull(), im guessing there is no easy way to do this then?  Most of the tips I have gotten are to simply disregard it.  I appreciate the help on isFull() and will use your tips, I'm just asking this questions for personal knowledge.

3. Gary you also mentioned, "Note that your current push doesn't return a value when it succeeds."  Refer to above post for better context. - - do you mean that I should return something when it succeeds? I didn't think it was necessary, either you or someone else can comment on this.

Thanks again,
Ben
0
 
LVL 30

Expert Comment

by:Mayank S
ID: 8237412
Your push () function can be simply implemented as:

template <class ItemType>
void Stack :: push ( ItemType item )
{
  Node * temp = new (nothrow) Node ;

  if ( temp == NULL )
    throw STACK_IS_FULL ; // end if

  else
  {
    temp -> value = item ;
    temp -> next = top ;
    top = temp ;

  } // end else

} // end of push ()

As for the pop () method, I don't think there needs to be any modification in that, and I guess you can let it be as it is.

As for the push () returning a value, maybe that you can give it a bool return-type:


template <class ItemType>
bool Stack :: push ( ItemType item )
{
  Node * temp = new (nothrow) Node ;

  if ( temp == NULL )
    return false ; // end if

  else
  {
    temp -> value = item ;
    temp -> next = top ;
    top = temp ;
    return true ;

  } // end else

} // end of push ()

Now, wherever you called your push () function, just check if the value returned is true or false. If true, then its fine, otherwise there was a problem in allocation.

Mayank.
0
 
LVL 15

Accepted Solution

by:
efn earned 120 total points
ID: 8237459
Hi Ben,

1.  There is no right or wrong on this.  It's kind of a matter of taste and the expected environment of use.  A class like this is generally designed to be reused in multiple programs, possibly by multiple people.  You have to try to guess what the people using it will want.  If it throws an exception, will they be happy because it helps them debug their errors?  Or will they be annoyed that their programs blow up?  Or will they be annoyed that they have to bother with try/catch code to prevent the exception from blowing up the program?

Yet another design that might be desirable in some environments is to use an assert facility.  For example, in the pop function, you could code

assert(!isEmpty());

The standard assert macro evaluates its argument and calls abort() if the result is false, unless NDEBUG is defined, in which case, it does nothing.  Thus, you can build a debugging version of the program that helpfully blows up when an assertion is not true, and from the same source code, you can build a production version that relentlessly slogs on even if an assertion is false.

2.  The way you implemented isFull is pretty easy, it's just not reliable, and so probably not very useful.  To decide what isFull should return with the current design, you have to be able to determine whether a memory allocation will succeed at some indeterminate future time.  In general, you can't do that, because unknown other threads or processes may be allocating and deallocating memory unpredictably meanwhile.

3.  The compiler should require that a function return what it is declared to return.  That means that if it returns void, the compiler should not allow it to return -1, and if it returns int, the compiler should not tolerate a return statement that doesn't specify a value (or no return statement at all, which does the same thing).  So push can be declared to return either void or int, but then all the return statements inside the function have to conform to the declaration.  In your push function before the latest one (which I think is the one Gary was looking at), the function was declared to return void, but the error path returned -1.  I think Gary saw that, figured you meant the function to return int, and pointed out with that assumption that the other path would also have to return some value.

--efn
0
 
LVL 6

Expert Comment

by:GaryFx
ID: 8241185
Actually, the comment I had on push related to your original version, and not the later one that throws instead.  But I think efn and others have clarified things very well.  (Better than I have time to.)

Gary
0
 

Author Comment

by:killer455
ID: 8242476
Just out of interest.

 Node * temp = new (nothrow) Node ;

 if ( temp == NULL )
   throw STACK_IS_FULL ; // end if

The allocation fails if temp==NULL.  Well how would you say that the allocation succeeds?  Would it be...   if(temp!=NULL)

??
0
 
LVL 15

Expert Comment

by:efn
ID: 8243015
Yes.  Or if you want to be more obscure:

if (temp)
0
 
LVL 30

Expert Comment

by:Mayank S
ID: 8243224
Otherwise, let the condition be the same (temp == NULL ).... if it goes to the else statement, it succeeds :-)
// that's what we're doing above too

Mayank.
0
 

Author Comment

by:killer455
ID: 8243365
Ok I think I'm going to end this question, problem is everyone has contributed, is there a way to split the points?
0
 
LVL 30

Expert Comment

by:Mayank S
ID: 8243385
Post a question on the Community Support area, requesting them to refund you half the points, and put a link to this question over there too. They'll help you out with how to go about the rest.

Mayank.
0
 

Expert Comment

by:modulo
ID: 8246958
Dear killer455

I've refunded 25 points to enable you to accept the comment for one expert and to post a "Points for <expertname>" Q for the other expert in the same topic area.

Please:
1) Post the link to the original Q in the "Points for <expertname>" and
2) Add in the original Q a comment with the link to the "Points for <expertname>", thus the email notif will warn the expert.

modulo

Community Support Moderator
Experts Exchange
0

Featured Post

Free Tool: Subnet Calculator

The subnet calculator helps you design networks by taking an IP address and network mask and returning information such as network, broadcast address, and host range.

One of a set of tools we're offering as a way of saying thank you for being a part of the community.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

When writing generic code, using template meta-programming techniques, it is sometimes useful to know if a type is convertible to another type. A good example of when this might be is if you are writing diagnostic instrumentation for code to generat…
Basic understanding on "OO- Object Orientation" is needed for designing a logical solution to solve a problem. Basic OOAD is a prerequisite for a coder to ensure that they follow the basic design of OO. This would help developers to understand the b…
The viewer will learn how to use the return statement in functions in C++. The video will also teach the user how to pass data to a function and have the function return data back for further processing.
The viewer will learn additional member functions of the vector class. Specifically, the capacity and swap member functions will be introduced.
Suggested Courses

800 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question