IBM面试问题：如何在一个堆栈进行排序？

本文介绍了IBM面试问题：如何在一个堆栈进行排序？的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述

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

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 code到实现这种算法是（原谅我的生锈Ç技能）：

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