I am trying to implement a stack using a set of sub-stacks of fixed length. For the sub-stack, I use a simple array of fixed length initialized in the constructor. For the stack, I use a vector of sub-stacks.
The below push method tries to allocate memory to a new substack and push it to the vector. But whenever a new push happens (let's say on vector setofstacks[1], the previous setofstacks[0] gets garbage values by the substack destructor being called. Not sure why this happens.
vector<substack<T>> setofstacks;
substack<T> *s = new substack<T>(size);
setofstacks.push_back(*s);
setofstacks[currStackIndex].push(elem);
On the other hand, if I convert the object to object pointer of substack and store that in the vector, that works perfectly well.
vector<substack<T>*> setofstacks;
setofstacks.push_back(new substack<T>(size));
setofstacks[currStackIndex]->push(elem);
Not working full code
/* Program: Implement a stack of substacks of fixed size
*
* Date: 12/28/2015
*/
#include <iostream>
#include <vector>
using namespace std;
template <class T>
class substack
{
private:
T *arr;
int nextAvailable;
int size;
public:
substack(int capacity);
~substack();
void push(T elem);
T pop();
T peek();
bool isfull();
bool isempty();
};
// Constructor initializing size of substack
template <class T>
substack<T>::substack(int capacity)
{
nextAvailable = 0;
size = capacity;
arr = new T[capacity];
}
// Destructor freeing memory allocated by the stack implemented using array
template <class T>
substack<T>::~substack()
{
delete[] arr;
arr = NULL;
}
// Pushing an element on top of a substack of fixed size
template <class T>
void substack<T>::push(T elem)
{
if (nextAvailable < size)
{
arr[nextAvailable] = elem;
nextAvailable++;
}
else
{
cout << "Substack is full" << endl;
return;
}
}
// Popping the top element from a stack of fixed size
template <class T>
T substack<T>::pop()
{
nextAvailable--;
if (nextAvailable >= 0)
{
T del = arr[nextAvailable];
arr[nextAvailable] = NULL;
return del;
}
else
{
cout << "Stack is empty" << endl;
return NULL;
}
}
// Peeking the top element from a stack of fixed size
template <class T>
T substack<T>::peek()
{
if (nextAvailable > 0)
{
return arr[nextAvailable - 1];
}
else
{
cout << "Stack is empty" << endl;
return NULL;
}
}
// Checking if a substack is full or not
template <class T>
bool substack<T>::isfull()
{
return (nextAvailable == size);
}
// Checking if a substack is empty or not
template <class T>
bool substack<T>::isempty()
{
return (nextAvailable == 0);
}
template <class T>
class SetOfStacks
{
private:
//vector<substack<T>*> setofstacks;
vector<substack<T>> setofstacks;
int currStackIndex;
int size;
public:
SetOfStacks(int capacity);
~SetOfStacks();
void push(T elem);
T pop();
T peek();
};
// Constructor initializing a set of stacks
template <class T>
SetOfStacks<T>::SetOfStacks(int maxStackCapacity)
{
currStackIndex = 0;
size = maxStackCapacity;
substack<T> *s = new substack<T>(maxStackCapacity);
setofstacks.push_back(*s);
//setofstacks.push_back(new substack<T>(maxStackCapacity));
}
// Destructor clearing set of stacks vector
template <class T>
SetOfStacks<T>::~SetOfStacks()
{
setofstacks.clear();
}
// Pushing an element on top of a stack implemented by a set of fixed length substacks
template <class T>
void SetOfStacks<T>::push(T elem)
{
if (!setofstacks[currStackIndex].isfull())
{
setofstacks[currStackIndex].push(elem);
}
else
{
currStackIndex++;
substack<T> *s = new substack<T>(size);
setofstacks.push_back(*s);
//setofstacks.push_back(new substack<T>(size));
setofstacks[currStackIndex].push(elem);
}
}
// Popping an element from top of a stack implemented by a set of fixed length substacks
template <class T>
T SetOfStacks<T>::pop()
{
if (!setofstacks[currStackIndex].isempty())
{
return setofstacks[currStackIndex].pop();
}
else
{
setofstacks.pop_back();
currStackIndex--;
if (currStackIndex >= 0)
{
return setofstacks[currStackIndex].pop();
}
else
{
cout << "Stack is empty" << endl;
return NULL;
}
}
}
// Peeking an element from top of a stack implemented by a set of fixed length substacks
template <class T>
T SetOfStacks<T>::peek()
{
return setofstacks[currStackIndex].peek();
}
int main()
{
SetOfStacks<int> *s = new SetOfStacks<int>(5);
s->push(1);
s->push(2);
s->push(3);
s->push(4);
s->push(5);
s->push(6);
s->push(7);
s->push(8);
cout << s->pop() << endl;
cout << s->pop() << endl;
cout << s->pop() << endl;
cout << s->pop() << endl;
cout << s->pop() << endl;
cout << s->pop() << endl;
cout << s->pop() << endl;
cout << s->pop() << endl;
s->push(1);
s->push(2);
s->push(3);
cout << s->pop() << endl;
cout << s->pop() << endl;
cout << s->pop() << endl;
//cout << s->pop() << endl;
system("pause");
}
Output
8
7
6
-572662307
-572662307
-572662307
-572662307
-572662307
3
2
1
Press any key to continue . . .
Working Code
/* Program: Implement a stack of substacks of fixed size
*
* Date: 12/28/2015
*/
#include <iostream>
#include <vector>
using namespace std;
template <class T>
class substack
{
private:
T *arr;
int nextAvailable;
int size;
public:
substack(int capacity);
~substack();
void push(T elem);
T pop();
T peek();
bool isfull();
bool isempty();
};
// Constructor initializing size of substack
template <class T>
substack<T>::substack(int capacity)
{
nextAvailable = 0;
size = capacity;
arr = new T[capacity];
}
// Destructor freeing memory allocated by the stack implemented using array
template <class T>
substack<T>::~substack()
{
delete[] arr;
arr = NULL;
}
// Pushing an element on top of a substack of fixed size
template <class T>
void substack<T>::push(T elem)
{
if (nextAvailable < size)
{
arr[nextAvailable] = elem;
nextAvailable++;
}
else
{
cout << "Substack is full" << endl;
return;
}
}
// Popping the top element from a stack of fixed size
template <class T>
T substack<T>::pop()
{
nextAvailable--;
if (nextAvailable >= 0)
{
T del = arr[nextAvailable];
arr[nextAvailable] = NULL;
return del;
}
else
{
cout << "Stack is empty" << endl;
return NULL;
}
}
// Peeking the top element from a stack of fixed size
template <class T>
T substack<T>::peek()
{
if (nextAvailable > 0)
{
return arr[nextAvailable - 1];
}
else
{
cout << "Stack is empty" << endl;
return NULL;
}
}
// Checking if a substack is full or not
template <class T>
bool substack<T>::isfull()
{
return (nextAvailable == size);
}
// Checking if a substack is empty or not
template <class T>
bool substack<T>::isempty()
{
return (nextAvailable == 0);
}
template <class T>
class SetOfStacks
{
private:
vector<substack<T>*> setofstacks;
int currStackIndex;
int size;
public:
SetOfStacks(int capacity);
~SetOfStacks();
void push(T elem);
T pop();
T peek();
};
// Constructor initializing a set of stacks
template <class T>
SetOfStacks<T>::SetOfStacks(int maxStackCapacity)
{
currStackIndex = 0;
size = maxStackCapacity;
//substack<T> *s = new substack<T>(maxStackCapacity);
setofstacks.push_back(new substack<T>(maxStackCapacity));
}
// Destructor clearing set of stacks vector
template <class T>
SetOfStacks<T>::~SetOfStacks()
{
setofstacks.clear();
}
// Pushing an element on top of a stack implemented by a set of fixed length substacks
template <class T>
void SetOfStacks<T>::push(T elem)
{
if (!setofstacks[currStackIndex]->isfull())
{
setofstacks[currStackIndex]->push(elem);
}
else
{
currStackIndex++;
//substack<T> *s = new substack<T>(size);
setofstacks.push_back(new substack<T>(size));
setofstacks[currStackIndex]->push(elem);
}
}
// Popping an element from top of a stack implemented by a set of fixed length substacks
template <class T>
T SetOfStacks<T>::pop()
{
if (!setofstacks[currStackIndex]->isempty())
{
return setofstacks[currStackIndex]->pop();
}
else
{
setofstacks.pop_back();
currStackIndex--;
if (currStackIndex >= 0)
{
return setofstacks[currStackIndex]->pop();
}
else
{
cout << "Stack is empty" << endl;
return NULL;
}
}
}
// Peeking an element from top of a stack implemented by a set of fixed length substacks
template <class T>
T SetOfStacks<T>::peek()
{
return setofstacks[currStackIndex].peek();
}
int main()
{
SetOfStacks<int> *s = new SetOfStacks<int>(5);
s->push(1);
s->push(2);
s->push(3);
s->push(4);
s->push(5);
s->push(6);
s->push(7);
s->push(8);
cout << s->pop() << endl;
cout << s->pop() << endl;
cout << s->pop() << endl;
cout << s->pop() << endl;
cout << s->pop() << endl;
cout << s->pop() << endl;
cout << s->pop() << endl;
cout << s->pop() << endl;
s->push(1);
s->push(2);
s->push(3);
cout << s->pop() << endl;
cout << s->pop() << endl;
cout << s->pop() << endl;
cout << s->pop() << endl;
system("pause");
}
Output
8
7
6
5
4
3
2
1
3
2
1
Stack is empty
0
Press any key to continue . . .
Please let me know what I am missing about using push_back while adding actual substack object so that it does not mess up the previous index substack in the vector.
Not sure how is this a dupe of rule of three. Am I missing one of the three - copy constructor, assignment operator? Please help me understand.
