![]() ![]() giving each stack it's own contiguous block of memory. ![]() You could create arbitrarily complex schemes similar to the one described above, but without knowing any more constraints for the posed question, I'll stop here.ĭue to the comments below, which do have a very good point, it should be added that interspersing is not necessary, and may even degrade performance when compared to a much simpler memory layout such as the following: +-+-+-+-+-+-+-+-+-+-+-+-+-+. Of course, this scheme is going to waste space, especially when the stacks have unequal sizes. Elements of the first stack are at indices i * 3, elements of the second stack are at indices i * 3 + 1, elements of the third stack are at indices i * 3 + 2 (where i is an integer). However, you could "intersperse" the stack elements. To know the next array element to use for this stack.Īlthough probably this will lead to less shifting, the implementation is not homogeneous for the three stacks, and inhomogeneity (you know) leads to special cases, more bugs and difficulties to maintain code.Īs long as you try to arrange all items from one stack together at one "end" of the array, you're lacking space for the third stack. In this case, you'll need to store the number n of elements on the middle stack and use the function: f := 1/4 ( (-1)^n (-1 + 2 n) + 1) + BS3 | Elem 6 | Elem 4 | Elem 2 | Elem 0 | Elem 1 | Elem 3 | Elem 5 | The resulting stack structure will be something like: The shifting is done with an equal space partitioning policy, although other strategies could be chosen depending upon your problem heuristics.įollowing suggestion, the middle stack could be implemented using an alternating sequence for subsequent pushes. You need to store the stack top for the first two stacks, and the beginning and end of the third stack in some structure.Ībove you may see an example. 1) Define two stacks beginning at the array endpoints and growing in opposite directions.Ģ) Define the third stack as starting in the middle and growing in any direction you want.ģ) Redefine the Push op, so that when the operation is going to overwrite other stack, you shift the whole middle stack in the opposite direction before Pushing. ![]()
0 Comments
Leave a Reply. |
AuthorWrite something about yourself. No need to be fancy, just an overview. ArchivesCategories |