Dynamic memory issues

[jwolfe]

I'm working on a dynamic stack, and I keep getting a heap corruption error when expandStack() is called.

const int INIT_STACK = 200;
class stack {
private:
	char* data;
	int top;
	void expandStack();
public:
	stack();
	~stack();
	bool push(char x);
	char pop();
	bool isEmpty();
};
stack::stack()
{
	top = -1;
	data = new char[INIT_STACK];
}
stack::~stack()
{
	delete[ ] data;
}
void stack::expandStack()
{
	char* newdata = new char[top+INIT_STACK+1];
	for(int i=0;i<top+1;i++)
	{
		newdata[i] = data[i];
	}
	delete [ ]data; // this line causes the error
	data = newdata;
}
bool stack::push(char x)
{
	if (top == INIT_STACK)
		expandStack();
	data[++top] = x;
	return true;

}
char stack::pop()
{
	if (top == -1)
		return 'z';
	return data[++top];
}
bool stack::isEmpty()
{
	if (top == -1)
		return true;
	return false;
}

main looks something like this

	stack myStack;
	myStack.push('s');
	for(int i=0;i<198;i++)
	{
		myStack.push('t');
	}
	myStack.push('t');
	myStack.push('t');
	myStack.push('t');
	myStack.push('t');
	myStack.push('t');
	myStack.push('x');

[m4ster r0shi]

What's the value of MAXSTACK?

EDIT: If it's bigger than INIT_STACK you have heap corruption, caused by data[++top] = x;

[jwolfe]

sorry, that's a typo. MAXSTACK should be INIT_STACK

[m4ster r0shi]

Well, it works ok for me... No problem at all. I'll take a closer look and tell you if I find anything. By the way, your pop function should look like this:

char stack::pop()
{
    if (top == -1)
        return 'z';
    return data[top--];
}

But that's irrelevant to the problem...

EDIT: Also, your push function should look like this:

bool stack::push(char x)
{
    if (top == INIT_STACK-1)
        expandStack();
    
    data[++top] = x;
    return true;
}

You see, in your version, when top==INIT_STACK-1 expandStack() won't be called and data[++top]=x; is equivalent to top++; data[INIT_STACK]=x; which can also cause heap corruption.

[jwolfe]

Awesome. Thanks for your help!
For anyone interested, the final version looks like this:

const int INIT_STACK = 200;
class stack {
private:
	char* data;
	int top;
	void expandStack();
public:
	stack();
	~stack();
	bool push(char x);
	char pop();
	bool isEmpty();
};
stack::stack()
{
	top = -1;
	data = new char[INIT_STACK];
}
stack::~stack()
{
	delete[ ] data;
}
void stack::expandStack()
{
	char* newdata = new char[top+INIT_STACK+1];
	for(int i=0;i<top+1;i++)
		newdata[i] = data[i];
	delete[ ] data;
	data = newdata;
}
bool stack::push(char x)
{
    if (top % INIT_STACK-1 == 0)
        expandStack();
    data[++top] = x;
    return true;
}
char stack::pop()
{
    if (top == -1)
        return 'z';
    return data[top--];
}
bool stack::isEmpty()
{
	if (top == -1)
		return true;
	return false;
}