The worst case analysis of algorithm on multiple stacks manipulation (Q1201875): Difference between revisions

System developers frequently encounter programs which involve multiple stacks, each of which has dynamically varying size. In such a situation, keeping multiple stacks in a common area with sequential allocation with cause some trouble. A number of possible solutions for overflow have been suggested. \textit{D. E. Knuth} proposed a simple solution in reallocating memory by move operations [The art of computer programming. Vol. 1: Fundamental algorithms (1968; Zbl 0191.179)]. The method will be described in detail in the next section. He also analyzed the average number of movements when overflow occurs and got a formula concerning the number of stacks and pushed items. Here, we focus on the worst sequence of pushed data instead of the individual worst case, getting some interesting properties.