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

Question

我得到了一个任务堆栈数排序a中使用两个栈升序排列的整数a和b.

使用11个操作:

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. 存款准备金率: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);
    }
}

我的函数对堆栈进行排序,我认为排序需要太多步骤.我需要有关如何使用较少的步骤对堆栈进行排序的建议或建议. 完整的在线代码

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中

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