Thursday 8 September 2011

Implement N stacks using one array

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;
}

No comments:

Post a Comment