StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>Answer 1: store the K stack pointers at the start. now mark the first address after that as address 0 (makes life simpler) an even K stack (stack_0, stack_2, ...) should grow upward; an odd K stack (stack_1, ..) should grow downward when initializing segment the array into K/2 parts (assuming K is even for simplicity). stack0 starts at address 0 stack1 starts at (arraySize / (k/2)) and grows downward stack3 starts at (arraySize / (k/2)) and grows upward</p> <p>when pushing data into a certain stack we should make sure that it is not overflowing to the adjacent stack, otherwise throw an exception. </p> <p>the array should look like this: [[stack pointers][stack_0][stack_1]...[stack_k]] where stack[0] and stack[1] both share the same region so they can make an optimal use of the space available to them.</p> <p>there could be further optimizations done by pairing each large stack with a small stack (this could be done by checking the behavior of the stacks over time). Also, grouping together rapidly changing arrays with slow changing arrays may help. </p> <p>Answer 2: thinking some more on this, I saw that my 1st solution only guarantees using array_size/(k/2) (since if we only have one array of size array_size/(k/2), we will get a stack overflow). the following (completely impractical) solution can satisfy the requirements: we allocate the start of the array for our k stack pointers, and ignore this region from now on. In the rest of the array we look at each cell as a struct [data, previous, next].</p> <p>push(stack_i, data) -> get sp_i from the stack pointers area. then go to that address, fill in the "next" pointer to point to the next empty cell in the array (we could have all the empty spaces linked together in another stack so this is o(1)). in the "next" cell store our data, and fill in the "prev" pointer. update sp_i</p> <p>pop(stack_i) -> get sp_i. get the "data" from that cell. "prev" from that cell is our new sp_i. push the old (now empty) cell to the empty list.</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload