Data Structures, Algorithms, & Applications in C++
Chapter 8, Exercise 25
First observe that at most
n - 1 cars can get on to the stacks
because at least one car must go directly from the input track to the
output track. Therefore, the size each track need be at most
n - 1.
The first track can get this many cars. This happens when the
input permutation is [1, 2, 3, ..., n].
With this permutation, cars
2, 3, ...,
and n get added to stack 1.
Whenever a car is added to stack 2, stack
1 contains one or more cars.
So stack 2 can get at most
n - 2 cars. It gets this many when the
input permutation is [1, 3, 4, ..., n, 2].
In general the ith stack can get at most
n - i cars and so its
size must be at least this much.
The input permutation
[1, i + 1, i + 2, ..., n, i,
i - 1, ..., 2] represents the worst case for stack
i.