不使用额外的数据结构对栈元素进行排序

按照升序对栈进行排序，也就是说，最大元素在栈顶。最多只能使用一个额外的栈来存放临时数据，但是不能使用额外的数据结构，比如数组来保存临时数据。严格要求只能使用O(1)的额外临时空间外加一个O(n)的栈。

假设我们待排序的栈是s1，额外有一个栈s2，s1是无序的，s2是有序的。
考察s1栈顶的元素，pop出来放到临时变量tmp里面，peek s2的栈顶元素，和tmp进行比较，如果比tmp大，那么就pop出来并且push到s1里面，循环，直到s2的栈顶比tmp，然后把tmp push到s2里面，至此，s1里面的tmp按照顺序进入到了s2中。外层再来一层循环，对s1的每个元素进行同样的处理。

static Stack<int> Sort(Stack<int> s)
{
    var result = new Stack<int>();

    while (s.Count != 0)
    {
        var tmp = s.Pop();
        while (result.Count != 0 && result.Peek() > tmp)
        {
            s.Push(result.Pop());
        }
        result.Push(tmp);
    }

    return result;
}

这个算法的时间复杂度是O(n^2)，空间复杂度是O(n)，用了一个额外的栈，再有就只有了一个临时变量存放数据。