在堆栈中交替显示顶部和底部

Question

我正在做这个练习，在这个练习中，我必须交替显示堆栈顶部的元素，然后是底部的元素，直到它是空的。我仍然发现很难利用递归来解决这些练习，我想知道是否有人可以帮助我。我不能使用循环，只是递归。这是说明：“给定stack_t抽象数据类型及其定义的操作：创建，顶部，推送，弹出，元素（返回堆栈中元素的数量），破坏：完成接收堆栈并显示堆栈中交替启动的项的one_and_one函数用顶部元素，然后用底部元素，直到堆栈是空的”。这就是我想出的：

void one_and_one(stack_t* stack){

  if(!stack || elements(stack) == 0) return;

  int aux = top(stack);
  pop(stack);
  one_and_one(stack);
  printf("%i\n", aux);
}

在打印底部之前，我还需要弄清楚如何打印顶部的。我将给出一个例子，以便更好地理解它。如果我有以下堆栈（1是最上面的元素）：|1 | | 2 | | 3 | | 4 | | 5 | | 6 | | 7 |输出必须如下：1,7,2,6,3,5,4。不管怎样，谢谢！

Answer 1

如果操作可能是破坏性的——也就是说原始堆栈预计不会保持完整，那么下面是一个算法思想：

1. 显示堆栈顶部

下面是一个伪代码：

function one_and_one(stack)
    if empty(stack)
        return
    print (pop(stack))        // Step 1
    stack2 = create_stack()   // Step 2
    copy_stack(stack2, stack) // Step 3
    destroy_stack(stack)      // Cleanup
    one_end_one(stack2)       // Step 4


/* This is a helper function for step 3 - recursive as well because no loops allowed*/
function copy_stack(dest, src)
   if not empty(src)
      push(dest, pop(src))

顺便说一句，我觉得把它想象成一个玩具堆叠金字塔是很方便的，你被要求交替取顶部和底部。你拿另一个“空”金字塔。取第一个金字塔的顶部，然后逐个移动到另一个金字塔。重复第二个金字塔。这也暗示了你可以只使用两个堆栈，而不是每次创建一个。