Answer 1: keep the K stack pointers at the beginning. now mark the first address after that as address 0 (simplifies life) the even stack K (stack_0, stack_2, ...) should grow up; the odd stack K (stack_1, ..) should grow down when initializing the array segment in the K / 2 part (assuming K is even for simplicity). stack0 starts at address 0 stack1 starts at (arraySize / (k / 2)) and grows down stack3 starts at (arraySize / (k / 2)) and grows up
when pushing data onto a specific stack, we must make sure that it does not overflow the neighboring stack, otherwise it will throw an exception.
the array should look like this: [[stack pointers] [stack_0] [stack_1] ... [stack_k]], where stacks [0] and stack [1] use the same region so that they can optimally use the available to them space.
further optimizations can be made by pairing each large stack with a small glass (this can be done by checking the behavior of the stacks over time). It can also help group fast-changing arrays with slowly-changing arrays.
Answer 2: thinking about this, I saw that my 1st solution only guarantees the use of array_size / (k / 2) (since if we only have one array of size array_size / (k / 2), we get a stack overflow ) The following (completely impractical) solution can satisfy the requirements: we allocate the beginning of the array for our pointers to k and ignore this region. In the rest of the array, we consider each cell as a structure [data, previous, next].
push (stack_i, data) -> get sp_i from the stack pointer area. then go to this address, fill in the “next” pointer to point to the next empty cell in the array (we could have all the empty spaces connected together on another stack, so this is o (1)). in the "next" cell store our data and fill in the "prev" pointer. sp_i update
pop (stack_i) -> get sp_i. get the "data" from this cell. "prev" from this cell is our new sp_i. click on the old (now empty) cell in the empty list.