c - 如何仅使用堆栈操作对堆栈进行排序？

Question

我在网上找到了这个问题。

给定一个栈S，写一个C程序对栈进行排序(升序排列)命令)。我们不允许对堆栈的实现方式做出任何假设。唯一要使用的函数是:

Push
Pop
Top
IsEmpty
IsFull

我认为我们可以构建堆并对其进行排序。对此的最佳解决方案是什么？

Answer 1

假设这里唯一允许的数据结构是 Stack，那么你可以使用 2 个 Stack。

迭代直到原栈为空，每次迭代，从原栈中弹出一个元素，当第二个栈中的栈顶元素大于被移除的元素时，弹出第二个栈并将其压入原栈。现在您可以将您最初从原始堆栈弹出的元素推送到第二个堆栈。

这种方法的时间复杂度是 O(N^2)。

实现这个算法的 C 代码是(原谅我生疏的 C 技能):

void SortStack(struct Stack * orig_stack)
{
  struct Stack helper_stack;
  while (!IsEmpty(orig_stack))
  {
    int element = Pop(orig_stack);
    while (!IsEmpty(&helper_stack) && Top(&helper_stack) < element)
    {
      Push(orig_stack, Pop(&helper_stack));
    }
    Push(&helper_stack, element);
  }
  while (!IsEmpty(&helper_stack))
  {
    Push(orig_stack, Pop(&helper_stack));
  }
}