Was wondering how this can be done using C++.
Divide given array into 3 parts - (0 - N/3), (N/3 - 2N/3) , (2N/3 - N). How would i keep track of the overflow?
Thanks Kelly
2
-
So all the stacks are equal in size and are not growable. Right?Mahesh– Mahesh2011-08-22 14:39:02 +00:00Commented Aug 22, 2011 at 14:39
-
Yes. Lets say the array size is 300.Kelly– Kelly2011-08-22 14:40:26 +00:00Commented Aug 22, 2011 at 14:40
Add a comment
|
1 Answer
You must necessarily maintain a pointer-to-top for each of your stacks. Why not just check that these pointers don't exceed their bounds?
answered Aug 22, 2011 at 14:41
Oliver Charlesworth
274k34 gold badges591 silver badges687 bronze badges
7 Comments
Oliver Charlesworth
@Kelly:
void push(int stacknum, T data) { if (top[stacknum] == (N/3)*stacknum) { error("overflow"); } else { /* Push */ } }.
Voo
Certainly a possibility that way, but if you "sacrifice" one word per stackpart you can avoid having the user keep track of the stacknum somewhere. A negligible overhead for a much nicer API imho.
Oliver Charlesworth
@Voo: I was assuming all of this would be encapsulated in a struct somewhere, along with a nice interface that hides all the details!
Kelly
@Oli, but how do i find the index of the top element? I have tried something like this. In order to maintain the pointer , i have declared another array(not sure if this is the right way) int *arrayPointer[3] = { NULL, NULL ,NULL }; // Initially pointing NULL Let size of each stacks be 300, so my array size would be 3 * Size of each stack. int sizeOfStack = 300; int *buffer = new int [ 3 * sizeofStack ]; I am blank after this. void push ( int stackNum, int value)
Oliver Charlesworth
@Kelly: You can either maintain pointers, or indices. Pointers would be:
for (i = 0; i < 3; i++) { arrayPointer[i] = &buffer[sizeofStack*i]; }. Indices would be: int arrayIndices[3]; for (i = 0; i < 3; i++) { arrayIndices[i] = sizeofStack[i]; }. |