three stacks in an array

[suresha_psg]

hi

Implementing two stacks in an array is simpler. One stack at one end of array and another stack at another end of array(decreasing it). And there is only one overflow condition(if top1>top2).

Can anyone suggest me a way to implement three stacks in an array efficiently? One way i could think of is to split array as 1/3,1/3,1/3 fixed size array. But its inefficient.

Another way is to implement two stacks as before and make another stack as intermediate. that is insert one element on left side and insert another element in right side of middle. But its too complex.

Is there any other way?

[Hnefi]

Why would you want several stacks in one array? Why not three dynamic arrays?

But anyway, you could make each element in the three stacks contain a pointer to the next element in that stack. Then you can simply let each stack write to the first empty space in the array. Or, to prevent clumping, you could hash each new element into the array.

[suresha_psg]

Its a problem given in Tanenbaum Book. I came around while reading. To share all of our views i put this question.

[suresha_psg]

Well. I think of another way like using a method that classful IP addressing scheme uses. that is extracting the MSB and if its 1 it can be designated as first stack. Am I right with this approach? Will it work well?

[RoboTact]

Was there more difinite question? I would place a restraint like this: given array of N bytes, create that structure supporting 3 stacks of total size N requiring additional O(log(N)) memory (or another - possible - amount of memory) and O(1) time for push/pop operation.
I can't figure it with O(log(N)), there is obvious solution with O(N) (linked list with blocks of one byte), there is simple solution with O(sqrt(N)) (linked list of blocks of size sqrt(N) and troubleshooting block with linked list for each byte, which may contain bytes of any stack).

[sam_guru]

make two stacks from end of arrays & another one at the middle of array. Programm this array in a such a way that stack at the middle should check that wheather there is any space at its two ends or not. If it has an space at first end then & no space at another end then if you want to put an element then the middle stack should be shift by one element towards first end. So that the other end of middle stack will become blank & you can push element in that.

[RoboTact]

make two stacks from end of arrays & another one at the middle of array. Programm this array in a such a way that stack at the middle should check that wheather there is any space at its two ends or not. If it has an space at first end then & no space at another end then if you want to put an element then the middle stack should be shift by one element towards first end. So that the other end of middle stack will become blank & you can push element in that.Aha, shift middle stack for O(1). :rolleyes:

[DragForce]

You have an array of N bytes. Divide it by M blocks of K bytes. Each block will be called a page.
Create an array of M elements, ith element of which will identify which stack uses ith page.
Create an array of M elements, ith element of which will identify the number of previous page used by the stack which uses page i.
Create 3 pointers - heads of stacks which will point to the first elements of the first 3 pages.
Create 3 pointers - bottoms of stacks which will point to the first elements of the first 3 pages.

As soon as a stack runs out of the curent page a new page is given to it and the head jumps to the next page.

Provided that M is fixed and is independent of N we have O(1) of extra memory used. All complexity characteristics of the stack structure are satisfied.

[RoboTact]

You missed overhead with partially filled pages. By your model only single stack can own entire page, and what happens when we run short on pages? It's O(K)=O(N) memory overhead.

[DragForce]

Very good point.

I have got the following ideas how to modify my approach.

1. We can get rid of "an array of M elements, ith element of which will identify which stack uses ith page." It does not give any value.
2. As soon as we ran out of free pages and one stack reached the end of its last page split the remaining free space into M new smaller pages storing the fixed number of extra information to be able to rewind the stacks.
3. Continue doing 2. unless we ran out of free space at all.

The memory consumed by auxilary data will be O(log_M(N)) = O(log N).