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

Question

我在网上发现了这个问题.

给定堆栈S,编写C程序以对堆栈进行排序(按升序排列).我们不允许对堆栈的实现方式做任何假设.唯一要使用的功能是:

Push
Pop
Top
IsEmpty
IsFull

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

Answer 1

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

迭代直到原始堆栈为空并且在每次迭代中,从原始堆栈弹出元素,而第二个堆栈中的顶部元素大于移除的元素,弹出第二个堆栈并将其推送到原始堆栈.现在,您可以将最初从原始堆栈弹出的元素推送到第二个堆栈.

该方法的时间复杂度为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));
  }
}

Answer 2

给定这些堆栈操作,您可以编写递归插入排序.

void sort(stack s) {
    if (!IsEmpty(s)) {
        int x = Pop(s);
        sort(s);
        insert(s, x);
    }
}

void insert(stack s, int x) {
    if (!IsEmpty(s)) {  
        int y = Top(s);
        if (x < y) {
            Pop(s);
            insert(s, x);
            Push(s, y);
        } else {
            Push(s, x);
        }
    } else {
        Push(s, x); 
    }
}

Answer 3

它可以使用相同的堆栈递归完成.O(n ^ 2)我用C++编写了它,但是转换为C是微不足道的.我只是喜欢模板,你确实用C++标记了你的问题

template<typename T>
void Insert(const T& element, Stack<T>& stack)
{
  if(element > stack.Top())
  {
    T top = stack.Pop();
    Insert(element, stack);
    stack.Push(top);
  }
  else
  {
    stack.Push(element);
  }
}

template<typename T>
void StackSort(Stack<T>& stack)
{
  if(!stack.IsEmpty())
  {
    T top = stack.Pop();
    StackSort(stack);
    Insert(top, stack);    
  }    
}

编辑得到我的投票!:))