dynamic stack using vector strategy

[bunnyboy]

So, i wrote stack, which is using vector strategy in case of being too small. The code compiles well and works until the resize function is called to resize the size of array. Tnx for any help solving this error.

#ifndef STACK_H
#define STACK_H

const int DEFAULT_SIZE = 10;

template <typename T>
class stack
{
private:
	T *array;
	int top_, size;

public:
	stack(): top_(-1), size(DEFAULT_SIZE) { array = new T[DEFAULT_SIZE]; };
	~stack(){ delete [] array; array = NULL; };

	void push(const T &a)
	{
		if ( top_ == size )
			resize();

		array[++top_] = a;	 
	}

	void resize()
	{        
		int newSize = size + (size / 2);
		T *newArray = new T[newSize];

		const T *fromArray = array;
		T *toArray = newArray;

		for(int i = 0; i < size; i++)
			*(toArray++) = *(fromArray++);

		delete fromArray;
		delete toArray;
		delete [] array;

		array = newArray;
		size = newSize;                     
	}

	void pop(){ top_--; }

	T top() const
	{
		if ( top_ >= 0 ) 
			return array[top_];
	}

	bool empty()
	{
		if ( top_ < 0 ) 
			return true;
		else 
			return false;
	}
};

#endif

[Ancient Dragon]

lines 36 and 37: delete these lines because they are just a temp pointers and can not be deleted.

[bunnyboy]

It still crashes ...

[ArkM]

That's it:

if ( top_ == size )
    resize();

See what happens:
0. empty stack of size 1 (for simplicity); top_ = -1
1. push; top_ != size, OK, top_ = 0 now, stack full!
2. push again: WARNING: top_ != size, NO resize!!! ...
... and you overwrite allocated memory ...

I think it's so easy to correct the code.
Do it yourself ;)

[bunnyboy]

I still do not quite understand what is wrong. I was working seperate on the resize function and came up with that:

#include <iostream>
using namespace std;

int* resize( int &oldSize, int currentIndex, const int *array )
{
	int newSize = oldSize + 10;
	oldSize = newSize;
	
	int *newArray = new int[newSize];
	
	for(int i = 0; i < currentIndex; i++)
	{
		*(newArray + i) = *(array + i);
	}
	
	return newArray;	
}

int main()
{
    int DEFAULT_SIZE = 10;
    int size = 500;
    
    int *array = new int[DEFAULT_SIZE];
    
    for(int i = 0; i < size; i++)
    {
    	if( i == DEFAULT_SIZE )
    	{
    		int *tmp = resize(DEFAULT_SIZE, i, array);
    		delete [] array;
    		array = tmp; 
    		
    	}

    	*(array+i) = i;
    }
    
    for(int i = 0; i < size; i++)
     	cout << *(array + i) << " ";

    
    cin.get();
    return 0;
}

And it is working, but when I implement it into my stack, problem persist. So if I am right, there is something wrong with top being initialized to -1. Still I do not know exactly how that could affect it, but obvious it does. I think that is the thing @ArkM was talking about. Can someone explain it to me more in details. Thanks!

[ArkM]

Better YOU take a paper and a pencil and try to push 2 elements in the stack with DEFAULT_SIZE == 1. Do it step by step and see that you DON'T RESIZE a stack when the 2nd element is added.

[bunnyboy]

if ( top_ == (size -1) ) ... :$

[bunnyboy]

Here is my final code ... feel free to comment it, suggest any improvements that can be made... I will appreciate it. Thank you ArkM, for your assistence!:icon_wink:

#ifndef STACK_H
#define STACK_H

template <typename T>
class stack
{
private:
	T *array;
	int Top, size;

	T* resize( int &oldSize, int currentTop, const T *array )const
	{
		int newSize = oldSize + 10;
		oldSize = newSize;

		T *newArray = new T[newSize];

		for(int i = 0; i <= currentTop; i++)
		{
			*(newArray + i) = *(array + i);
		}

		return newArray;	
	}



public:
	stack(int default_size = 10): Top(-1), size(default_size) { array = new T[default_size]; };
	~stack(){ delete [] array; array = NULL; };

	void push(const T a)
	{
		if( Top == (size-1) )
		{
			T *tmp = resize(size, Top, array);
			delete [] array;
			array = tmp; 

		}

		array[++Top] = a;	 
	}

	void pop(){ Top--; }

	T top() const
	{
		if ( Top >= 0 ) 
			return array[Top];
		else return 0;
	}

	bool empty()
	{
		if ( Top < 0 ) 
			return true;
		else 
			return false;
	}
};

#endif

[ArkM]

class Stack // Capitalize the name, there is class stack in STL
{
  ...
  bool empty() const { return Top < 0; }
  ...
};

It's C++, not Pascal ;)

[bunnyboy]

I named it in lower case, because I had to write a rpn, which is using STL libraries and mine. So now I just change include directive without changing other things.

There is one more question I have... in queue I implement pop function this way:

void pop()
{
	for ( int i = 0; i < Top; i++ )
		array[i] = array[i+1];
	Top--;
}

and I am wondering if there is any better way of doing this or this is the only option. ( you might say, use linked list, I know, it is better tool for this assignment, but I tried to do it this way to and I did :) plus I learned something new from it :icon_cheesygrin: )