CareerCup

i think it can be done in many ways ..
most simplest form will be
define element as follows
stact1=for every (i%3==0)
stack2=for every (i%3==0) + 1
stack3=for every (i%3==0) + 2
three seprate first and last is initilaized accordingly .

each stack pointer is incremented or decremented in steps of 3.
Also check is put so that stack pointer do not exceed array limit;

how about create 3 linked list? which is most efficient for add and remove(push, pop).

The question is to implement stack with array not with link list.IT means it have the property of LIFO only.In arrays we actually don't delete the items but restrict the front end to access elemnets above top of the current stack.When we add an element we just overwrite the value of stack and increase the value of front end.i.e we try to give property of LIFO only.
stack implemented with array is faster than stack implemented with link list .
if any one better idea , can share with us .

one thin more .. if stack is implemented with link list then the link list must be doubly link list(if u want to make code efficient)
the other way i.e. in singly link list ,addition is very easy and set front end pointer to the top of the stack but
in case of delete operation we have to create one extra temporary pointer which transverse through link list until its's next equl to top of stack and then space(item) is deleted(top of stack), further value to top of stack pointer(front end ) is assigned to the value of temporary stack (front end) pointer.
but in both cases efficiency wil be less than arrays

If you want to implement a stack using an array, how much memory are you supposed to allocate for this array? If I keep calling PUSH, the array will soon be out of memory and you have to allocate a new one.
To amortize this, everytime the array is full, you have to allocate twice as much memory as the previous array.

You are wasting memory on something that doesn't need random access. With a linked list, you're not wasting any memory.

"A Stack is usually implemented with a Linked List. You always Push and Remove at the head."

Everytime you push into the stack, make that element the Head. Everytime you pop from the stack, remove the Head. All constant time. No searching.

Using a linked list, you are wasting only a few more instructions compare to the array method but on a 1 gig machine, to execute a single instruction is 1 nsec = (1/1,000,000,000) sec. A few more instructions aren't that big of a deal.

one stack starts from left end: top1 = top1++; 2nd stack starts from right end: top2=top2--; Now the 3rd stack will be started from mid position of the array(i.e n/2 location). while push, top3 = n/2>= top3?n-top3:n-top3+1. while pop, top3 = n/2>= top3?n-top3:n-top3+1. Need to implement the boundary conditions....

This solution looks to be weird , uneven distribution for all the stack .

Assuming that it is to be implemented using array(question is that way), i think the better solution wud be d combination of ideas from guest(Post 1) and sathesh(Post 11).
take two stacks pointers from left(these moves to right on push)
stact1=for every (i%2==0)
stack2=for every (i%2==0) + 1

and stack3 from end of the array(moves to the left on push)
this way we are utilising the memory more efficiently(we need to check it out if its true bcos it may change depending on how number of elements in each stack grow)
the condition to check if the corresponding stack is full or empty can be changed accordingly.

The first solution with

stact1=for every (i%3==0)
stack2=for every (i%3==0) + 1
stack3=for every (i%3==0) + 2

looks the best

Stack1 grows from the left end and Stack2 from the right end. Stack3 grows on either side of the mid position.

Every alternate PUSH into Stack3 is done using 2 Top variables. First PUSH happens on left of the mid and next to the right and so on. The currently active Top for Stack3 is determined by a 'flag'.

In all the solns provided above, a definite bound is defined on all the stacks by dividing the array into 3 equal portions. However it is not known which stack would use up most space.. say stack A need has n-2 elements in the array at any point, and stack B and C need only 1 element each.
So i suggest pushing elements for all three stacks into the same array contiguously, but each element should maintain an offset pointing to the next element belonging to the same stack as itself. 3 global variables can be maintained and updated as push/pop operations occur on all 3 stacks.
Example: So when the top of stack A is to be popped,
1. the global variable for A (gvarA) is accessed and its offset is found
2. the corresponding element(tosA) is accessed, the offset of the next element it is poiting to is written into the gvarA and tosA is popped.
3. if the popped element was the topmost element in the array, then alls fine. else, it created a hole in the array that needs to be plugged for effiecient mem. usage.
4. so the topmost element in the array is is written into the hole created and the global variable for the corresponding stack is updated. The offset present in this element(pointing to the next element) is also updated relatively.

Notes:
- calculating and updating the offsets are trivial O(1) operations and do not add complexity to pop() or push(), which remain O(1) stack operations
- the algorithm uses the array space very efficiently without statically allocating space for each of the 3 arrays
- Disadvantage however is that it requires O(n) space to store the offsets. storing the relative offsets between elements and not the actual memory address can significantly reduce the space reqd.

I don't think the first solution is good, and I am surprised why so many people support it. With this solution, you're assuming 3 stacks increase evenly. For this solution, for the worse case, you're only going to use 1/3 of the total space to get full - which is very INEFFICIENT.

The best solution should use all the spaces before any one of the 3 stacks report full.

Sathesh's solution is good, but somebody called it weird.

If i understand Khoa's solution of using linked list correctly, it uses extra memory. When we already have an array, then each array index will be encapsulated in linked list node. Besides the node has a pointer to the next node. His solution would work when you have to design a stack class from stratch where you are not given an array, rather the stack class manages its memory internally.

An efficient solution is to adjust the length of the individual stack objects. Basically, you have a continuous block of memory & they want to see how efficiently you can use it. This block of memory i.e. the array needs be "adapted" like a Stack class. "Adapt" because usually one instance of a regular Stack class will use the entire block of memmory. but here the same block of memory has to be shared by 3 instances of your special Stack class

Basically, this

Most importantly, everyone here uses the memory in 3 equal parts. This is completly wrong. Perhaps instance 2 of stack class is being used in the context where application is reading all values from a file etc & pushing it in the Stack. But instance 1 of stack class can push things only when certain condition/attributes on some computation is true. i.e instance 2 is using more memory than instance 1. So we cannot partition the memory in 3 equal parts.

I can give more insight on this. Let say you have this special singleton class, StackAdapter with Push, Pop, Remove operations derived from the interface of Stack.

If we focus only on 3 stack problem, all we need to do is -

1) maintain 2 data memebers which represents the max size of 2 instances of Stack. [ maximum size of 3rd instance of stack can be computed because we know the size of Array]
2) Maintain 3 data members which represents 3 the used size of all 3 instances.
3) You already have the pointer to the block of memory [I assume the block of memory is initialized with some default value of -1 or say null etc.]
4) Basically, 1st 2nd & 3rd instances of Stack will have some predefined max length. But this maximum length is not constant. They will change based on the usage.
5) Instance 1 of Stack class memory range is 0th index of array to maxLen1. Instance 2 of stack class memory range = maxLen1 +1 to maxLen2 & 3rd instance memory range = maxLen2 + to Size of array.
6)StackAdapter has a method GetNewStack/CreateNewStack. The class contains a static data member which knows how many instances of stack has been used. If instanceCount < 3 it will return the client code a stack instance. Note - We will always give the 2nd instance [ i.e memory pointing from maxLen1 + 1 to maxLen2 ] as the last instance.
7) Client1 calls StackAdapter.GetNewStack & starts pushing the values.
8) Instance 1 of Stack starts from 0 to maxSize1 [ i.e left to right ] so on every push operation we increment the count usedLen1++. if usedLen1 == maxLen1 this is the boundary condition. So we check that memory maxLen+1 still has the default value with which it was initialized. If yes, readjust the length of stack 1 & stack 2 instances i.e we decrement the maxLen2 for instance 2 & increment maxLen1 for Stack1. [ Note - you can impelement some Strategies pattern as how much offset you want when stack size grows beyond its max size]
9) To remove any item from instance 1 of stack class, simply decrement the count usedLen-- & set the memory to some default null or -1 values.
10) Another thread or client code calls StackAdapter.GetNewStack(). Your adapter returns the 3rd instance [ & NOT the 2nd instance ] of stack. The 3rd instance of stack moves right to left. So on ever push operation usedLen3 decreases. Your boundary condition is if( usedLen3 == 0 or in other words usedLen3 = maxLen2] check array[maxLen2] still holds the default value with which it was set. If yes, this means instance 2 of stack class has not been used. Then again readjust the size of instance 2 & instance 3 as per step 8) & continue push operation.
11) The remove for instance 3 is same as remove for instance 1 except usedLen3 will be incremented.
12) Only when the client application/code calls your StackAdapter 3rd time you return the 2nd instance of stack i.e memory from maxLen1+ 1 to maxLen2. Since, at step 8) & step 10) if usedLen > maxLen we do check whether 2nd instance of stack is in use or not, we know the ingetrity of memory range for 2nd instance is good.

This is the basic rough solution good enough from the interview perspective. But its implementation has to consider a lot of boundary condition such as what if stack 2 is getting used more than stack 3 or stack 1. This means we have to decrement max length for instance 1 or instance 3 depending upon whether stack 2 is moving left to right or right to left.

So i see a lot of starategies [boundary if else condition] & we can put it in an Strategy abstraction pattern. On similar view our stack class actually has to share memory between 3 instances [ or some maxNumOfStack instances]. So we need to adapt Stack interface to provide this functionality

Well it is true that if the stacks are of not equal size then %3 solution will be not work but adding this little feature might make it work

stact1=for every (i%3==0)
stack2=for every (i%3==0) + 1
stack3=for every (i%3==0) + 2

at the same time have three global variables maintaing the number of values in each stack.

While reading the elements from the array initially check if the 3 global variables are greater than zero ..... if so then access the elements for each stack by the above relation and then reduce the 3 global pointers by 1 and now again check whether > 0 .if so continue the i%3 process if any one of the global variables is zero then the particular stack is done so from here onwards i%2 for the rest of the two stacks ,,, simmilarly if at any point two of the global variables are zero then i%1 for the left out stack........

I cogitate it works

Maybe this makes sense:
1. Stack 1 grows from left to right.
2. Stack 3 grows from right to left.
3. Stack 2 grows from middle to either side.
First element goes to mid (say index p)
Second element goes to p=p+1
Third element goes to p=p-2
Fourth goes to p=p+3
Fifth goes to p=p-4
.
.
See the pattern. p points to the top of stack 2 all the time. A Global variable 'factor' initially contains 1. factor changes by adding 1 to its absolute value each time and flipping the sign. Pop works the same way. Subtract 1 from the absolute value of the factor and flip the sign.
Off course every time you PUSH you have to check that the stacks do not write on each others valid values.

Special cases:
if stacks 2 and 3 grow much faster than stack 1, then 2 and 3 hit each other earlier than 1 and 2. Now all we have to do is move the elements of stack 2 to the left(at least by 1, possibly more if 2 and 3 will hit again sooner than 1 and 2). Note that decrementing 'p' by 1 for each empty cell reclaimed between stacks 1 and 2 will keep our stack 2 valid. 'factors' are relative and does not change by these shifts.

There is one more thing that might look odd. Stacks 1 and 3 have their bottom-most cell fixed, but for stack 2 it starts at mid of array and possible changes. So what if Stack 2 empties out completely, and then starts to grow again. Where will it grow from since its last base position *may* have been claimed by either of the other 2 stacks. One simple way is to get the current tops of the stacks 1 and 3. Find the midpoint of the remaining gap, and start the base of stack 2 from there...

Long story :)... does it make sense?

Nopes the above one fails...Consider an array of size 6 (for simplicity a small size is considered). Now, according to you p is the center. In this case it will be 3.(n/2)
If you go on filling up 2nd and 3rd by doing p+1, p+3 and .. p-2, p-4 resp. then the positions p+2 and p-1 are left unfilled. and in no standart arthmetic operation can be accessed.

Accoding to me the soln would be like this

1. Assume as there are two partition one is of size 1/3rd and other of 2/3rd

2. Stack1 move from left to right in first partition
Stack2 move from left to right in 2nd partition
Stack3 move from rght to left in 2nd partition
3. By doing this we allow one to use atlest 1/3 space but at its also possible for other two stack to use combinely there space

Doesn't matter where in the array the values are stored as long as the three heads are maintained

As items are pushed you either ...
Find the first "Hole" or Append to the end of the array

S1 Push Push S1,S1
S2 Push Push Push S1,S1,S2,S2,S2
S3 Push S1,S1,S2,S2,S2,S3
S1 Push S1,S1,S2,S2,S2,S3,S1
S2 Pop S1,S1,S2,S2,(*),S3,S1 (*) is a "Hole"
S3 Push S1,S1,S2,S2,(S3),S3,S1 (S3) Inserted into Hole S3 Head updated

Every so often you can flatten the array space (Compact Memory) to remove the holes

I think this is an exercise in memory managment rather than Stacks

Doc

I guess the first solution given is the best....I don't understand why people are talking about linked list when the ques says to use an array. With dividing the array in 3 parts makes it easier to add and delete elements by maintaining three pointers each one of them pointing to the top of the one of the three stacks....

I have gone thru all the solutions .. and in my humble opinion, JH's solution seems best. All u really need are three counters and few calculation checks. Remember: We are implementing stacks, so we are guaranteed to have one dimensional increase only. Keeping the bases of the three stacks as left right and middle makes perfect sence. We need three counters to track the top of stacks.

An alternate solution is to divide the memory into equal size pages of a reasonable size. Say for an array of 100, we have pages of size 10. For each page, we will need only one element to point to the last page.

In this case, there will be limited internal fragmentation but no external fragmentation.

This solution works elegantly for any number of stacks to be implemented in an array.

Do you think it is cheating to use a multidimensional array?

I feel Vel's soln is the best of all... ( and it is what I also had thought of :) )

Why not use a 3-d array? Each stack for each dimension?

How abt this ? As mentioned earlier, one stack grows from 0th element, the second from the last element and third from middle element to either side of the stack. Now lets say last-element stack is huge and first and middle are small. Then when last-stack fills up, move the middle element stack towards left. The ideal place for the middle stack's new starting point will be in the middle of the blank spaces (to its left). The relocation is not a big deal - O(mid stack size)

So, the problem boils down to dealing with middle stack. We need to keep track of the begining of middle stack (initially, middle element of the array). And an addressing scheme. Lets say 1000(=mid stack start MSS) is the middle element. Then i=1 element must be in 1001 (MSS + 1). The i=2 will be 999 (MSS - 1). i=3 will be 1002 (MSS + 2). In general, for an i-th element, it is MSS - (-1^i)*(int)(i+1/2). (have'nt tested the general formula, but you get the idea, rt ? besides, since we only have to keep track of TOS w.r.t MSS, it can be easily done with comparison - i.e to which side of the start it lies, use that offset on the either side + 1)

This method efficiently uses memory. Only overhead is when one of the side stack fills up, you have to move the mid stack

guys i think the solution by Guest (1st one),then Satesh and finally Vel's is the one that sounds to wokr fine...rest sux

Guys we can easily do this in following manner

1.

Guys we can easily do this in following manner

1. start 1st stack from front end of array.
2. Start 2nd stack from back end of array.
3. Make a circular array stack in between s1 and S2.

Plz comment......

Regards,

The first stack will grow from the last element.
Second and third will grow from the first element but with a special node in between after specific interval to keep track of which node belongs to which stack by manipulating bits in this special node. This will also allow to easily "compact" the stack if one of the stack reduces in size.

for example lets say array is of 4bit integer and we have to push following nodes S1,S2,S2,S3,S2,S3,S1 then array would be like

0100-S2-S2-S3-S2-0001-S3........-S1-S1

an index will be maintained for both side

1. Stack1 starts from left. Top1, Bottom1
2. Stack2 starts from right. Top2, Bottom2
3. Stack3 starts from center. Top3, Bottom3

|1| <-- Top1, Bottom1
| |
| | <-- Top3, Bottom3
| |
|5| <-- Top2, Bottom2

A. push1() ~ ++Top1
>> if Top1 == Bottom3, shift all elements between Bottom3 and Top3 one
position below, provided (Top3 + 1 != Top2) else "Stack Full"
>> insert at Top1
B. push2() ~ ++Top2
>> if Top2 == Top3, shift all elements between Bottom3 and Top3 one
position up, provided (Bottom3 - 1 != Top1) else "Stack Full"
>> Top2 -= 2. // Compensate 1 for ++ and other for shift.
>> insert at Top2
C. push3() ~ ++Top3
>> if Top3 == Top2, shift all elements between Bottom3 and Top3 one
position up, provided (Bottom3 - 1 != Top1).
>> Top3 -= 2. // Compensate 1 for ++ and other for shift.
>> insert at Top3

Pop are simpler.
Top1--; Top2++; Top3--;

I might have a solution for this.

1. Put the data in some sort of node which has value and previous pointer.

2. Have 3 pointers (top1, top2 and top3) which show the top of the stack, initially pointing to null.

3. As the node comes in, depending on which stack it has to go into, you change the pointer "top(i)".

4. All nodes point to the previous node. Whenever pop() on any stack is called, it will simply move top(i) node to the previous pointer.

5. Pushing the node is O(n) as you will have to go through all the nodes so see which one of the places in array are empty.

6. For count, you can either maintain another location for caching which will be O(1) in memory and time. Update this number as we pop or push.

//my solution to it

(1)array size may be anything
(2)init all array values to -1(for empty space)
(3)one entry of data takes 2 memory locations(even-odd pair)
(4)even position has index to its prev element and odd position has the data
(5)during pop return to the previous element using index of prev which is in even poistion(if its -1 stack is empty) and make the current elemnt to (-1, -1)
(6)when u push, search from beginning for (-1, -1) location to add
(7)each stack maintain its own top value
(8)push is O(n) time and pop is O(1) time
(9)like this way we can use whole array, watever the push and pop happens

EX:array with size 14 and 3 stacks1, s2 and s3, att top vals are -1 on start
s1.push(3);//-1 3 -1 -1 -1...top1=1
s2.push(5);//-1 3 -1 5 -1 -1 -1...top2=3
s2.push(7);//-1 3 -1 5 3 7 -1 -1 -1...top2=5
s1.push(8);//-1 3 -1 5 3 7 1 8 -1 -1 -1...top1=7
s2.pop() ; //-1 3 -1 5 -1 -1 1 8 -1 -1 -1...top2=1
s3.push(9);//-1 3 -1 5 -1 9 1 8 -1 -1 -1...top3=5
s1.push(4);//-1 3 -1 5 -1 9 1 8 7 4 -1 -1 -1...top1=9

comments are allowed

how abt this-->

4 pointers + 1 bool variable required.

initially:
pointer1 points to a[0] (stack1)
pointer2 points to a[n-1] (stack 2)
pointer3 & pointer 4 point at middle (stack3)

as we add something to
Stack1: we on the left side i.e. a[0],a[1] ---> towards right..pointer1 is top of stack1

Stack2: we add towards left <--- a[n-2], a[n-1] ..pointer 2 moves left and represents top of stack2

Stack3: we add on right first. set boolean variable say "topAtRight" = true. Next one is added to its left..now "topAtRight" = true as false.

if we fill up middle -->Right and there is space on left. And a number comes for stack2 everything in stack3 moves left to make space

if we fill up middle -->Left and there is space on right. And a number comes for stack1 everything in stack3 moves right to make space

space is most efficiently

How about maintain an array of N pointers.
Each pointer pointing to another array that would represent a stack.
In essence, it would be a 2-d array.Would require only as many elements that are required.
MAx size of the array would be Nx(Max number of elements in that can fit into stack)

#define Stack1 1
#define Stack2 2
#define Stack3 3
main()
{
int CountStack1=0;
int CountStack2=1;
int CountStack3=2;
Array[];
PushStack(Array,Val,Stack1,&CountStack1 );
PushStack(Array,Val,Stack2,&CountStack2 );
PushStack(Array,Val,Stack3,&CountStack3 );
PopStack(Array,Stack1,&CountStack1 );
PopStack(Array,Stack2,&CountStack2 );
PopStack(Array,Stack3,&CountStack3 );
}
PushStack(Array,Val,Stack,*Count)
{
switch(Stack)
{
case Stack1:
Array[Count ]=Val;
Count=Count+3;

break;

case Stack2:


Array[Count ]=Val;
Count=Count+3;
break;

case Stack3:
Array[Count ]=Val;
Count=Count+3;
break;

}
}
PopStack(Array,Stack,*Count)
{
switch(Stack)
{
case Stack1:
if(!Count)
Count=Count-3;
else
NoElement Break;

Array[Count ]=NULL;


break;

case Stack2:
if(Count>1)
Count=Count-3;
else
NoElement Break;

Array[Count ]=NULL;
break;

case Stack3:
if(Count>2)
Count=Count-3;
else
NoElement Break;
Array[Count ]=NULL;
break;

}
}

Link List for stack!! How Dumb.