如何仅使用堆栈操作对堆栈进行排序？ [英] How to sort a stack using only stack operations?

问题描述

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

I found this question on the web.

给出一个堆栈S，编写一个C程序对堆栈进行排序（以
升序排列）。
我们不允许对如何实现堆栈进行任何假设。
唯一要使用的功能是：

Given a stack S, write a C program to sort the stack (in the ascending order). We are not allowed to make any assumptions about how the stack is implemented. The only functions to be used are:

Push
Pop
Top
IsEmpty
IsFull

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

I think we can build heap and sort it. What is optimal solution to this?

推荐答案

假设此处允许的唯一数据结构是堆栈，则可以使用2个堆栈

Assuming that the only data structure allowed here is the Stack, then you could use 2 Stacks.

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

Iterate until the original stack is empty and in each iteration, pop an element from the original stack, while the top element in the second stack is bigger than the removed element, pop the second stack and push it to the original stack. Now you can push the element you originally popped off the original stack to the second stack.

此方法的时间复杂度为O（N ^ 2）。

The time complexity of this approach is O(N^2).

实现此算法的C代码将是（对不起我的C技能）：

C code to implement this algorithm would be (excuse my rusty C skills):

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));
  }
}

这篇关于如何仅使用堆栈操作对堆栈进行排序？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！