对堆栈进行排序

Question

我知道如何对数组进行排序，但我以前没有对堆栈进行排序。 所以请帮忙。如何使用快速排序算法对堆栈进行排序？ 谢谢。

Answer 1

“对堆栈进行排序”是什么意思？堆栈的整体思想是遵循后进先出 (LIFO) 顺序。使用堆栈的事物期望它们放入堆栈的最新事物将位于堆栈的顶部，较旧的事物位于其下方，按照它们插入的时间反向排序，因为这就是堆栈。如果你对堆栈进行排序，你就会破坏它。

Answer 2

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

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

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

---

如果您绝对不想使用列表，您可能会发现这个解决方案很有趣。 （盗自此处）：

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);
    }
} 

Answer 3

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

Answer 4

我编写了这个函数来使用 O(n) 空间对堆栈进行排序。这工作得很好。我将不胜感激任何及时的改进。现在是 O(n*n) 。

StackHead sortStack(StackHead s1){

StackHead s2=createStack();
Element a,b;

while(!isEmpty(s1)){

    a=top(s1);s1=pop(s1);
    if(isEmpty(s2) || top(s2) > a){
            s2=push(a,s2);
    } else {
            while(top(s2)<=a && !isEmpty(s2)){
                    b=top(s2); s2=pop(s2);
                    s1=push(b,s1);
            }

            s2=push(a,s2);

            while( (isEmpty(s2) || top(s1) < top(s2) ) && !isEmpty(s1)) {
                    b=top(s1); s1=pop(s1);
                    s2=push(b,s2);
            }
    }//end of else

}//end of outer while

return s2;

}