使用临时堆栈按升序对堆栈进行排序

Question

void sortStack(Stack *s)
{
    /* add your code here */
    Stack temp;
    temp.ll.head =NULL;
    temp.ll.size =0;
    int item_popped;
    int item_temp;
    while (isEmptyStack(s)!= 1) {
        item_popped = pop(s);
        if (isEmptyStack(&temp) == 1) {
            push(&temp,item_popped);
            continue;
        }
        item_temp = peek(&temp);
        if (item_popped > item_temp) {
            push(&temp,item_popped);
        }
        else {
            while(item_popped <= item_temp || isEmptyStack(&temp) != 1) {
                push(s,pop(&temp));
                item_temp = peek(&temp);
            }
            push(&temp,item_popped);
        }
    }
    while (isEmptyStack(&temp) != 1) {
        push(s,pop(&temp));
    }
}

假设，我的内置函数（例如 pop()、peek()、push() 等）是正确的，为什么这段按升序对堆栈进行排序的代码不起作用。排序后打印时我没有收到任何输出。例如，给定堆栈 1,4,5,3,2 --> 我想通过使用临时堆栈获得 5,4,3,2,1（按升序排列）。

Answer 1

两件事。首先，这是错误的：

else {
    while(item_popped <= item_temp || isEmptyStack(&temp) != 1) {
        push(s,pop(&temp));
        item_temp = peek(&temp);
    }
    push(&temp,item_popped);
}

想象一下进入那个 while 循环，两个条件都为真，但后者只为真，因为 temp 中只剩下一个元素。然后你弹出 temp 并推到 s。这使得 temp 为空。然后你 peek(&temp) 这是错误的，因为临时没有任何东西。结果是 peek returns 现在在 item_temp.

中的任何未指定的“东西”

那个循环应该是这样的：

else {
    while(item_popped <= item_temp) {
        push(s,pop(&temp));
        if (isEmptyStack(&temp) != 1)
            item_temp = peek(&temp);
        else break;
    }
    push(&temp,item_popped);
}

其次，您的比较逻辑会将列表排序升序，而不是像您预期的那样降序。我指出这一点是因为您的期望陈述完全矛盾。你说：

5,4,3,2,1（升序）

嗯..那不是“升序”。这是降序顺序。如果您期望 pop-loop 会报告 that 序列，那么所有比较都需要反向逻辑。如果你期待一个实际的 ascending 序列，我展示的更改代码应该这样做。

使用临时堆栈按升序对堆栈进行排序

Sorting a stack in ascending order using a temporary stack

c

sorting

linked-list

stack

fifo