Implementing a int stack in C++

Question

I came across a exercise on the web, this is the text:

Write a class int_stack that will manage a stack of integers. The integers values will be stored in a dynamically allocated array.

This class will propose the following member functions :

int_stack (int n) constructor that will dynamically allocate n integers,

int_stack ( ) constructor allocating 20 integers,

~ int_stack ( ) destructor,

int empty ( ) the return value is 1 if the stack is empty, 0 otherwise,

int full ( ) the return value is 1 if the stack is full, 0 otherwise,

void operator < (int p) pushes (add) the p value on the stack,

int operator >(int p) returns (and remove) the value on the top of the stack

I've tried to implement it, but the > (pull) operator won't work.

Here's my code:

int_stack.h

class int_stack
{
private:
    int* stack;
    unsigned int n, p;
    void init(unsigned int n);

public:
    int_stack(unsigned int n);
    int_stack();
    ~int_stack();
    int empty();
    int full();
    void operator <(int i);
    int operator >(int i);
};

int_stack.cpp

#include "int_stack.h"

void int_stack::init(unsigned int n)
{
    this->stack = new int[n];
    this->p = 0;
}

int_stack::int_stack(unsigned int n)
{
    this->init(n);
}

int_stack::int_stack()
{
    this->init(20);
}

int_stack::~int_stack()
{
    delete this->stack;
}


int int_stack::empty()
{
    return (this->p == 0 ? 1 : 0);
}

int int_stack::full()
{
    return (this->p == n-1 ? 1 : 0);
}

void int_stack::operator <(int i)
{
    if (!this->full())
        this->stack[p++] = i;
}

int int_stack::operator >(int i)
{
    if(!this->empty())
        return this->stack[p--];
    return 0;
}

What am I doing wrong?

Answer 1

In addition to getting the indexing right, the class needs a copy constructor and an assignment operator. As written you'll get multiple deletes of the same data block:

int_stack s0;
int_stack s1(s0); // uh-oh

Both destructors will delete the array allocated by the constructor for s0.

Answer 2

There are several major flaws with you code:

Unless you want to resize the stack every time you push or pop something onto or off of it, respectively, you probably want to use a linked-list- or deque- style storage structure instead of a vector/array-style.

Overloading operator< and operator> to do what amounts to extraction and insertion is a terrible interface choice. I would urge against using operators for those operations:

void int_stack::push(int i)
{
    // push an element onto the stack
}

int int_stack::pop()
{
    // pop an element off of the stack
}

Because you are not implementing it as a linked-list or deque, when you go to push elements, you can (and eventually will) attempt to write outside the bounds of the memory you allocated.

Finally, you do not delete your stack properly. If you use new [], you must also use delete [].

Answer 3

The choice of interface is quite bad, but ignoring that fact consider what your members mean, in particular p. The index p refers to the location above the last added element. When you return the value in the pop operation you are reading the value from that location, but that location does not have a value:

int int_stack::operator >(int i)
{
    if(!this->empty())
        return this->stack[p--];   // <-- predecrement!
    return 0;
}

Regarding the interface, operator< and operator> are unnatural choices for the push and pop operations. When someone reads in code s < 5 they interpret that you are comparing s with 5, not inserting an element into the stack s. That is going to be the source of confusion.

Worse than operator< is operator> defined as int operator>(int). User code to read a value will end up looking as:

value = s > 5;

That looks like comparing s to 5, and storing the result into value. Moreover, the actual behavior is completely independent on the argument 5, the same operation can be spelled as s > -1 or even s > 5.3

Answer 4

Here is the working implementation I came up with.

It implements a copy constructor and the assignment operator.

Also, the indexing works, and the interface has changed from the < and > operators to two simple push(int) and int pop() functions.

It throws exceptions when you try to push/pop over the boundaries.

int_stack.h

#include <exception>

class int_stack
{
private:
    int* stack;
    unsigned int n, p;
    void init(unsigned int n);
    void copy(int_stack& other);

public:
    int_stack(unsigned int n);
    int_stack();
    int_stack(int_stack& other);
    int_stack& operator=(int_stack& other);
    ~int_stack();
    int empty();
    int full();
    void push(int i);
    int pop();
    class OutOfBoundariesException: public std::exception {};
};

int_stack.cpp

#include "int_stack.h"

void int_stack::init(unsigned int _n)
{
    n = _n;
    stack = new int[n];
    p = 0;
}

int_stack::int_stack(unsigned int n)
{
    init(n);
}

int_stack::int_stack()
{
    init(20);
}

int_stack::int_stack(int_stack& other)
{
    copy(other);
}

int_stack& int_stack::operator=(int_stack& other)
{
    copy(other);
    return *this;
}

void int_stack::copy(int_stack& other)
{
    n = other.n;
    p = other.p;
    stack = new int[n];
    for (unsigned int i = 0; i < n; i++)
        stack[i] = other.stack[i];
}

int_stack::~int_stack()
{
    delete[] stack;
}

int int_stack::empty()
{
    return (p == 0 ? 1 : 0);
}

int int_stack::full()
{
    return (p == n ? 1 : 0);
}

void int_stack::push(int i)
{
    if (!full())
        stack[(++p)-1] = i;
    else
        throw new OutOfBoundariesException;
}

int int_stack::pop()
{
    if (!empty())
        return stack[(p--)-1];
    else
        throw new OutOfBoundariesException;

    return 0;
}