Thread: Please ..err..nitpick my code (implementing a stack)

I started reading up on data structures from scratch after some unconsolidated knowledge gathered from the web.
(If anyone is interested, the book I'm following is "Data Structure and program design in C++" --by Robert L. Kruse && Alexander J. Ryba)

Without further ado, here is my implementation of a stack..in a contiguous array.
(I know the exception handling can be done in a less lazy way.... would do that if I ever use this code in any program)

Code:

namespace mm
{


enum stack_error{overflow,underflow,beheaded};
    
template <typename T, int Size>
class stack
{
private:
    T mem[Size];
    int stack_ptr; // The offset from mem to get the pointer to the head
public:
    stack():stack_ptr(-1){};
    void push(const T& in)
    {
        if(++stack_ptr >= Size) throw(overflow);
        else mem[stack_ptr] = in;
    }
    T& head()
    {
        if(stack_ptr == -1) throw(beheaded);
        return mem[stack_ptr];
    }
    void pop()
    {
        if(--stack_ptr < -1 ) throw(underflow);
    }
    bool empty(){return stack_ptr==-1?true:false;};
    int size(){return stack_ptr+1;};
};
}

It worked nicely for all test cases I came up with.
Still.. to make sure...:
Am I doing something that is considered 'bad' in the norm ?

Originally Posted by manasij7479

I started reading up on data structures from scratch after some unconsolidated knowledge gathered from the web.
(If anyone is interested, the book I'm following is "Data Structure and program design in C++" --by Robert L. Kruse && Alexander J. Ryba)

Without further ado, here is my implementation of a stack..in a contiguous array.
(I know the exception handling can be done in a less lazy way.... would do that if I ever use this code in any program)

Code:

namespace mm
{


enum stack_error{overflow,underflow,beheaded};
    
template <typename T, int Size>
class stack
{
private:
    T mem[Size];
    int stack_ptr; // The offset from mem to get the pointer to the head
public:
    stack():stack_ptr(-1){};
    void push(const T& in)
    {
        if(++stack_ptr >= Size) throw(overflow);
        else mem[stack_ptr] = in;
    }
    T& head()
    {
        if(stack_ptr == -1) throw(beheaded);
        return mem[stack_ptr];
    }
    void pop()
    {
        if(--stack_ptr < -1 ) throw(underflow);
    }
    bool empty(){return stack_ptr==-1?true:false;};
    int size(){return stack_ptr+1;};
};
}

It worked nicely for all test cases I came up with.
Still.. to make sure...:
Am I doing something that is considered 'bad' in the norm ?

The most glaring problem is that by using an array of constant size, you limit yourself to using it with objects having only the most trivial construction requirements. For more complex types, it just doesn't make sense to have a default constructor called on each and every element, especially considering that they technically shouldn't even "exist" until they are actually pushed into the data structure by the programmer! So if I were to choose a fixed array, I'd simply declare it as an array of bytes, casting each element to the appropriate type and manually invoking constructors/destructors, as necessary.

Besides that, I would recommend using std::size_t instead of some signed integer type. Accessing the top element, checking bounds, etc is just as easy (without having to resort to that awkward -1 convention), and the intent is much clearer (you wouldn't declare an array of size, say, -1024, would you?).

Otherwise, the code seems fairly clear and concise. I would be a little more liberal with the spacing, personally, but that's just a matter of taste, I guess.

A few things I noticed:

1) C++ instantiates a separate body of code for each permutation of the template parameters. Thus, if a client wanted to have two stacks, say stack<int, 100> and stack<int, 1000> you'd end up with two copies of nearly identical code.

2) Do you want your users to be limited in the size of a particular stack? Probably not.

3) The exception of type "beheaded" is probably not familiar with most people. What does it mean?

The solution to problems 1) and 2) is to use a dynamically growing array, usually doubling each time it becomes full. You can get rid of the Size template parameter and just take a size argument in the constructor. This will reduce code bloat greatly. Also, it will eliminate the problem of requiring default constructors for T. On the other hand, your code complexity will increase.

Also, just to be a nitpick:

Code:

return stack_ptr == -1 ? true : false;

why not

Code:

return stack_ptr == -1;

Originally Posted by MacNilly

A few things I noticed:

1) C++ instantiates a separate body of code for each permutation of the template parameters. Thus, if a client wanted to have two stacks, say stack<int, 100> and stack<int, 1000> you'd end up with two copies of nearly identical code.

2) Do you want your users to be limited in the size of a particular stack? Probably not.

3) The exception of type "beheaded" is probably not familiar with most people. What does it mean?

The solution to problems 1) and 2) is to use a dynamically growing array, usually doubling each time it becomes full. You can get rid of the Size template parameter and just take a size argument in the constructor. This will reduce code bloat greatly. Also, it will eliminate the problem of requiring default constructors for T. On the other hand, your code complexity will increase.

Also, just to be a nitpick:

Code:

return stack_ptr == -1 ? true : false;

why not

Code:

return stack_ptr == -1;

1. && 2. Good idea.. will try to act on it.
3. It is just an enum declared on top and I got into some creative nomenclature; didn't derive exception classes because I wanted to keep it simple.
4. (return)
It was somewhat foolish coding on my part. :S .. though I changed it after being pointed out in this thread.