I have not compiled or tested the below code :-)
template<typename T> class MultiStack {
public:
MultiStack(int arraySize, int numberOfStacks);
~MultiStack();
void Push(const T & x, int i);
T Pop(int i);
private:
struct Node {
T data
Node * prev;
};
Node * Arr;
Node ** S;
Node * gptr;
};
/* MultiStack Constructor */
template<typename T> MultiStack::MultiStack (int arraySize, int numberOfStacks) {
// sanity checks
if (arraySize < 1) throw "MultiStack: arraySize must be greater than zero";
if (numberOfStacks < 1) throw "MultiStack: numberOfStacks must be greater than zero";
// allocate array
Arr = new Node[arraySize];
// initialize free stack: each prev points to next node in array
for(int n = 0; n < arraySize - 1; ++n) Arr[n].prev = &(Arr[n+1]);
Arr[arraySize - 1].prev = (Node *)NULL;
// allocate stack top pointers
S = new Node*[numberOfStacks];
// initialize stack top pointers to null
for(int i = 0; i < numberOfStacks; ++i) S[i] = (Node *)NULL;
// free stack top pointer points to first node of array
gptr = &(Arr[0]);
}
/* MultiStack Destructor */
template<typename T> MultiStack::~MultiStack() {
delete[] Arr; delete[] S;
}
/* MultiStack Push */
void template<typename T> MultiStack::Push (const T & x, int i) {
if (i < 0 || i >= sizeof(S)/sizeof(Node *)) throw "MultiStack: Push: Invalid Stack";
if (gptr == NULL) throw "MultiStack: Push: Array Space Exhausted";
// pop node from free stack
Node * temp = gptr;
gptr = temp->prev;
// assign value
temp->data = x;
// push node to given stack
temp->prev = S[i];
S[i] = temp;
}
/* MultiStack Pop */
T template<typename T> MultiStack::Pop (int i) {
// sanity checks
if (i < 0 || i >= sizeof(S)/sizeof(Node *)) throw "MultiStack: Pop: Invalid Stack";
if (S[i] == NULL) throw "MultiStack: Pop: Pop Attempted on Empty Stack";
// pop node from given stack
Node * temp = S[i];
S[i] = temp->prev;
// push node to free stack
temp->prev = gptr;
gptr = temp;
}
template<typename T> class MultiStack {
public:
MultiStack(int arraySize, int numberOfStacks);
~MultiStack();
void Push(const T & x, int i);
T Pop(int i);
private:
struct Node {
T data
Node * prev;
};
Node * Arr;
Node ** S;
Node * gptr;
};
/* MultiStack Constructor */
template<typename T> MultiStack::MultiStack (int arraySize, int numberOfStacks) {
// sanity checks
if (arraySize < 1) throw "MultiStack: arraySize must be greater than zero";
if (numberOfStacks < 1) throw "MultiStack: numberOfStacks must be greater than zero";
// allocate array
Arr = new Node[arraySize];
// initialize free stack: each prev points to next node in array
for(int n = 0; n < arraySize - 1; ++n) Arr[n].prev = &(Arr[n+1]);
Arr[arraySize - 1].prev = (Node *)NULL;
// allocate stack top pointers
S = new Node*[numberOfStacks];
// initialize stack top pointers to null
for(int i = 0; i < numberOfStacks; ++i) S[i] = (Node *)NULL;
// free stack top pointer points to first node of array
gptr = &(Arr[0]);
}
/* MultiStack Destructor */
template<typename T> MultiStack::~MultiStack() {
delete[] Arr; delete[] S;
}
/* MultiStack Push */
void template<typename T> MultiStack::Push (const T & x, int i) {
if (i < 0 || i >= sizeof(S)/sizeof(Node *)) throw "MultiStack: Push: Invalid Stack";
if (gptr == NULL) throw "MultiStack: Push: Array Space Exhausted";
// pop node from free stack
Node * temp = gptr;
gptr = temp->prev;
// assign value
temp->data = x;
// push node to given stack
temp->prev = S[i];
S[i] = temp;
}
/* MultiStack Pop */
T template<typename T> MultiStack::Pop (int i) {
// sanity checks
if (i < 0 || i >= sizeof(S)/sizeof(Node *)) throw "MultiStack: Pop: Invalid Stack";
if (S[i] == NULL) throw "MultiStack: Pop: Pop Attempted on Empty Stack";
// pop node from given stack
Node * temp = S[i];
S[i] = temp->prev;
// push node to free stack
temp->prev = gptr;
gptr = temp;
}
No comments:
Post a Comment