问对堆栈进行排序

EN

我知道如何对数组进行排序，但我以前没有对堆栈进行过排序。

最有效的解决方案可能是将数据结构更改为允许随机访问的列表，然后对列表进行排序。也就是说，就像这样：

1. 将堆栈中的所有元素放入数组中
2. 使用您知道的算法对数组进行排序。
3. 将所有元素放回堆栈中。

如果你绝对不想使用列表，你可能会发现这个解决方案很有趣。(从here窃取)：

void sort(stack)
{
    type x;

    if (!isEmpty(stack)) {
        x = pop(stack);
        sort(stack);
        insert(x, stack);
    }           
}

void insert(x, stack)
{
    type y;

    if (!isEmpty(stack) && top(stack) < x) {
        y = pop(stack);
        insert(x, stack);
        push(y, stack);
    } else {
        push(x, stack);
    }
} 

你说的“对堆栈进行排序”是什么意思？堆栈的整个思想是按照后进先出(LIFO)的顺序。使用堆栈的东西期望它们放在堆栈上的最新的东西将在堆栈的顶部，而旧的东西在它的下面，按照它们被插入的时间进行反向排序，因为这就是stacks 是。如果你对堆栈进行排序，你会打破它。

你能做的是..使用递归，递归地弹出堆栈中的元素，然后找到插入当前元素的最佳位置。如果您需要代码，请告诉我，但是在前面的评论中提到，对堆栈进行排序是完全不必要的:) :)