New answers tagged

3

Check amortized analysis. Note that usually array resizing requires (1) get memory for new version, (2) copy old contents over, (3) delete old version. The point of your approach 2 (double the size of the array each time, more generally extend by a fixed factor) is that it gives amortized constant cost for each push on the stack. The others get costlier when ...


2

Does this pseudocode help? Let me know of any clarifications. stack_0.push(0) // stack containing only vertex 0 stack_of_stacks = empty stack_of_stacks.push((stack_0, vertex 0)) // added a tuple of stack and vertex 0 while stack_of_stacks is not empty: (temp_stack, temp_vertex) = stack_of_stacks.pop() if temp_vertex = n-1 ...


Top 50 recent answers are included