用C按升序排序堆栈，使用两个堆栈
我被赋予了一项任务，即使用两个堆栈( a、a和b )按升序对整数的堆栈中的数字进行排序。
使用11项行动：
- sa：
swap a-交换堆栈a顶部的前2个元素 - sb：
swap b-交换堆栈b顶部的前2个元素。 - 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
回答 3
Stack Overflow用户
发布于 2016-07-02 22:48:41
给定两个堆栈A和B，其中A被随机排列元素填充，B为空，一个临时变量T能够容纳一个元素(和一个计数器，但计数器不算)，您可以通过以下方式将A按升序排序为B：
- 将所有元素从A移动到B，但保留T中最大的元素
- 将所有元素从B移动到A
- 将元素放在堆栈B上的T中
- 循环，直到A为空，
- 将所有元素从A移动到B，但保留T中最大的元素
- 将所有元素从B移动到A，但底部最大的元素除外(这里是计数器方便地保存B中已排序元素数量的地方)
- 将元素放在堆栈B上的T中
当然，您可以(而且应该)将所有这些都放在一个循环中。
Stack Overflow用户
发布于 2016-07-03 00:04:16
这实际上是两个队列问题，因为旋转操作有效地将堆栈转换为队列。在这种情况下，可以执行自下而上的合并排序，这将是相对快速的。
使用链接列表(而不是数组)来实现堆栈/队列将加快旋转速度。
两个队列的自下而上的合并排序：
初始拆分:将Pop元素从原始队列中删除，并将元素交替添加到原始队列和临时队列中。将队列大小设置为从原始队列中弹出的元素数。将排序运行大小设置为1。
合并传递:使用排序的运行大小来确定运行的大小，从每个队列合并运行，在原始队列和临时队列之间交替合并输出。双倍运行大小，如果运行大小为>=队列大小，请停止。
Stack Overflow用户
发布于 2017-02-24 03:50:47
以下是Java的解决方案。
public class SortStack {
Stack<Integer> stack1;
Stack<Integer> stack2;
public Stack<Integer> sort(Stack<Integer> stack) {
this.stack1 = stack;
stack2 = new Stack<>();
putSmallestAtBottom();
empty2BackTo1();
return stack1;
}
private void putSmallestAtBottom() {
/*Pop a number from stack1
* Compare it top item in stack2
* If stack2 item is bigger, move it stack1
* Keep doing this
* Once thats done push that smaller num to stack 2
* Keep repeating until stack 1 is empty*/
while (stack1.isEmpty() == false) {
int num = stack1.pop();
while (stack2.isEmpty() == false && stack2.peek() > num) {
stack1.push(stack2.pop());
}
stack2.push(num);
}
}
private void empty2BackTo1() {
while (stack2.isEmpty() == false) {
stack1.push(stack2.pop());
}
}
}https://stackoverflow.com/questions/38164849
复制相似问题
腾讯云开发者
Copyright © 2013 - 2026 Tencent Cloud. All Rights Reserved. 腾讯云 版权所有
深圳市腾讯计算机系统有限公司 ICP备案/许可证号：粤B2-20090059 
粤公网安备44030502008569号
腾讯云计算（北京）有限责任公司 京ICP证150476号 | 京ICP备11018762号