我的任务是使用两个堆栈 a
和 b
对整数堆栈 a
中的数字进行升序排序。
使用十一个操作:
- sa :
swap a
- 交换堆栈顶部的前 2 个元素a
- sb :
swap b
- 交换堆栈顶部的前 2 个元素b
。 - ss :
sa
和sb
同时发生。 - pa :
push a
- 取出b
顶部的第一个元素并将其放在a< 的顶部
。 - pb :
push b
- 将a
顶部的第一个元素放在b< 的顶部
。 - ra :
rotate a
- 将堆栈a
的所有元素向上移动 1。第一个元素变为 最后一个。 - rb :
rotate b
- 将堆栈b
的所有元素向上移动 1。第一个元素变为 最后一个。 - rr :
ra
和rb
同时出现。 - rra :反转
rotate a
- 将堆栈a
的所有元素向下移动 1。最后一个元素 成为第一个。 - rrb :反转
rotate b
- 将堆栈b
的所有元素向下移动 1。最后一个元素 成为第一个。 - 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
最佳答案
给定两个堆栈 A 和 B,其中 A 填充了随机排列的元素而 B 为空,并且一个临时变量 T 能够保存一个元素(和一个计数器但计数器不计数),您可以排序A按升序进入B:
- 将所有元素从 A 移到 B,但保留 T 中的最大元素
- 将所有元素从B移动到A
- 将T中的元素放入栈B
- 循环直到A为空
- 将所有元素从 A 移到 B,但保留 T 中的最大元素
- 将所有元素从 B 移动到 A,除了底部最大的元素(这里是计数器用来保持 B 中已排序元素数量的地方)
- 将T中的元素放入栈B
当然,您可以(并且应该)将所有这些放在一个循环中。
关于c - 使用两个堆栈在 C 中按升序对堆栈进行排序,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/38164849/