Double a Stack

[stoneJax]

I have a function push()that adds entries to a stack. I am trying to double the size of the stack when ever it becomes full. I can't put the function through debug mode because the compiler goes straight to this error, and I am not sure what to do about it.

Severity Code Description Project File Line Suppression State
Message Types pointed to are unrelated; conversion requires reinterpret_cast, C-style cast or function-style cast

template<class ItemType>
bool ArrayStack<ItemType>::push(const ItemType& newEntry)
{
	bool result = false;
	ArrayStack<ItemType>* newptr;

	if (top == capacity - 1)
	{
		newptr = new ArrayStack<ItemType>[capacity];
		
		memcpy(newptr, ptr, sizeof(ItemType) * capacity);
		delete[] ptr;
		ptr = newptr;
		top++;
		ptr[top] = newEntry;
		capacity *= 2;
	}


	if (top < DEFAULT_CAPACITY - 1)  // Does stack have room for newEntry?
	{
		top++;
		items[top] = newEntry;

		result = true;
	}  
	return result;
}  

[kbw]

memcpy(newptr, ptr, sizeof(ItemType) * capacity);
Don't use memcpy, copy the elements over one at a time. Why? Because objects usually can't be copied with memcpy.

Also, it's not obvious to me why lines 15/16 (the actual push) is there and not in left to the code below.

[dhayden]

Why is newptr defined at the top? You only need it when you have to expand the array.

Why is newptr a pointer to an array of arrays?? It should be a pointer to ItemType

Why do you allocate the same number of items as you currently have? I thought you were trying to allocate twice as many.

Why do you duplicate the code to actually insert the items?

Why do you compare top to DEFAULT_CAPACITY-1? That's basically saying that the default capacity is actually the maximum capacity. The ONLY place where you should use DEFAULT_CAPACITY is in the constructor.

Here is pseudo-code for what you want to do:

if (not enough room) {
    // allocate a new array with twice the capacity
    // copy the existing items one-by-one to the new array.
    // delete the old array
    // set ptr to the new array
    // set capacity to the new value
}

// Now you're guaranteed that there's enough room
top++
items[top] = newEntry;

[stoneJax]

Thanks for pointing out the flaws. I have reorganized my code as follows.

template<class ItemType>
bool ArrayStack<ItemType>::push(const ItemType& newEntry)
{
	bool result = false;

	ItemType* newStack = nullptr;
	if (top == capacity - 1)
	{
		capacity *= 2;
		newStack = new ItemType[capacity];
		
		for (int count = 0; count < capacity; count++)
		{
			newStack[count] = items[count];
		}
		delete[] items;
	}
	delete[] newStack;


	if (top < DEFAULT_CAPACITY - 1)  // Does stack have room for newEntry?
	{
		top++;
		items[top] = newEntry;

		result = true;
	}  
	return result;
}  

[dhayden]

This looks okay when there is enough capacity, but suppose your initial capacity is 10 and you have to resize. Here's what happens.
- Line 9 sets the (new) capacity to 20.
- Line 10 allocates space for 20 items.
- Lines 12-14 copy 20 items to the new array. There are only 10 items in the items array.
- Line 16 deletes the old array.
- Line 18 deletes the new array.
- Lines 21-24 insert the new item past the end of the (now deleted) items array.

To keep things straight, you might want to declare a separate newCapacity variable that contains the capacity of newStack. When you're done copying the data to newStack, do what's necessary to make newStack and newCapacity the actual stack and capacity.

Hope this helps.

[stoneJax]

Hi dhayden, I can see line 18 was a mistake now. I got rid of that and after delete[] items; I assigned items = newStack; . Also, while assigning one element at a time I changed the limit from capacity to top, since top is the last element that contains a value and that is what I am trying to copy in this loop. Then, I had the thought to add a for loop before this one that will iterate with capacity as the limit and initialize all the elements of newStack to NULL. Do you think this is a good idea or is it irrelevant?

Updated code:

template<class ItemType>
bool ArrayStack<ItemType>::push(const ItemType& newEntry)
{
	bool result = false;

	ItemType* newStack = nullptr;

	if (top == capacity - 1)
	{
		capacity *= 2;
		newStack = new ItemType[capacity];
		
		for (int count = 0; count < capacity; count++)
		{
			newStack[count]= NULL;
		}

		for (int count = 0; count < top; count++)
		{
			newStack[count] = items[count];
		}
		delete[] items;
		items = newStack;
	}




	if (top < capacity)  // Does stack have room for newEntry?
	{
		top++;
		items[top] = newEntry;

		result = true;
	}  
	return result;
}  

[dhayden]

I don't think you need to initialize the items in newStack to NULL, but it might be a good idea while debugging. You don't need to test at line 30. The code above that guarantees that there will be enough space by the time you get there.

[stoneJax]

Thank you for your help. I appreciate it!