c - 使用两个堆栈在 C 中按升序对堆栈进行排序

Question

我的任务是使用两个堆栈 a 和 b 对整数堆栈 a 中的数字进行升序排序。

使用十一个操作:

1. sa : swap a - 交换堆栈顶部的前 2 个元素 a
2. sb : swap b - 交换堆栈顶部的前 2 个元素 b。
3. ss : sa 和 sb 同时发生。
4. pa :push a - 取出 b 顶部的第一个元素并将其放在 a< 的顶部。
5. pb :push b - 将 a 顶部的第一个元素放在 b< 的顶部。
6. ra :rotate a - 将堆栈 a 的所有元素向上移动 1。第一个元素变为最后一个。
7. rb :rotate b - 将堆栈 b 的所有元素向上移动 1。第一个元素变为最后一个。
8. rr : ra 和 rb 同时出现。
9. rra :反转 rotate a - 将堆栈 a 的所有元素向下移动 1。最后一个元素成为第一个。
10. rrb :反转 rotate b - 将堆栈 b 的所有元素向下移动 1。最后一个元素成为第一个。
11. rrr : rra 和 rrb 同时出现。

我的排序函数

void    sorts_stack(stack *a, stack *b)
{
    int     srt;

    srt = is_not_sorted(a);
    if (srt)
    {
        if (a->list[srt] == top(a) && a->list[srt] > a->list[0])
        {
            rotate_ra_rb(a->list, a->size); //ra : rotate a
            putstr("ra\n");
        }
        else if (a->list[srt] == top(a) && a->list[srt] > a->list[srt - 1])
        {
            swap_sa_sb(a->list, a->size);//sa : swap a
            putstr("sa\n");
        }
        else if (a->list[srt] > a->list[srt - 1])
        {
            putstr("pb\n"); //pb : push b
            push_pb(a, b);
        }
        sorts_stack(a, b);
    }
    else if (b->size > 0)
    {
        if (top(a) < top(b))
        {
            push_pa(a, b); //pa : push a
            putstr("pa\n");
        }
        else if ((top(a) > top(b)) && b->size != 0)
        {
            push_pa(a, b); //pa : push a
            putstr("pa\n");
        }
        sorts_stack(a, b);
    }
}

我的函数对堆栈进行排序，我认为排序需要太多步骤。我需要关于如何以更少的步骤对堆栈进行排序的建议或建议。 complete online code

Answer 1

给定两个堆栈 A 和 B，其中 A 填充了随机排列的元素而 B 为空，并且一个临时变量 T 能够保存一个元素(和一个计数器但计数器不计数)，您可以排序A按升序进入B:

1. 将所有元素从 A 移到 B，但保留 T 中的最大元素
2. 将所有元素从B移动到A
3. 将T中的元素放入栈B
4. 循环直到A为空
   1. 将所有元素从 A 移到 B，但保留 T 中的最大元素
   2. 将所有元素从 B 移动到 A，除了底部最大的元素(这里是计数器用来保持 B 中已排序元素数量的地方)
   3. 将T中的元素放入栈B

当然，您可以(并且应该)将所有这些放在一个循环中。