如何仅使用Push，Pop，Top，IsEmpty，IsFull对堆栈进行排序？
给定堆栈S，需要仅使用Push ， Pop ， Top ， IsEmpty ， IsFull对堆栈进行排序。
寻找最简单的解决方案。
编辑：删除到位条件。 无法使用其他堆栈或队列。
可以办到…
好的：排序，ahem，“就地”只有列出的操作，不需要Top（）或IsFull（）或除调用帧之外的其他堆栈或数据结构。 （据推测， 作业问题的重点是要求递归解决方案。）
ruby
@a = [3, 2, 1, 6, 5, 4] class Array def empty? return size == 0 end end def sort e if @a.empty? @a.push e return end t = @a.pop if e > t @a.push(t).push(e) return end sort e @a.push t end def resort return if @a.empty? t = @a.pop resort sort t end p ['first ', @a] resort p ['final ', @a]
对于这个问题，我们可以考虑使用系统堆栈吗？ 进行几次递归调用。
public static void sort(Stack s) { if (!s.isEmpty()) { Integer t = s.pop(); sort(s); insert(t, s); } } private static void insert(Integer x, Stack s) { if (s.isEmpty()) { s.push(x); return; } if (x < s.peek()) { Integer t = s.pop(); insert(x, s); s.push(t); } else { s.push(x); } }
techInterview讨论 – 在堆栈上排序
比任何更多的伪，但有代码示例和可能的解决方案。
这是不可能的。
发生这种情况是因为你无法遍历堆栈，因为它必须到位（如果你使用额外的内存，你可以）。 因此，如果你无法遍历堆栈，你甚至无法比较堆栈的两个元素。 没有比较的排序需要额外的内存，因此也无法使用。
我也确定它不是功课，因为我不认为老师会给你一个无法解决的问题。
如果你真的必须只使用堆栈，只需使用1-2个额外的临时堆栈（我认为需要2个，但不是100％确定）并且这样做。
您可以使用哪些临时数据结构？ 使用push和pop，并且没有n个元素的临时存储，如果不存储其余部分，则无法访问堆栈底部附近的数据。
如果top （等于{x=pop();push(x);return x} ）被替换为shift ，那将是完全可行的 – 堆栈将变为fifo（shift + push; pop将被废弃）并且它可以在当前可用的元素上轻松实现。
你不能。 根据定义，如果不删除元素，则无法重新排序堆栈的内容。 push和pop也不是就地操作，所以基本上你要求用Top，IsEmpty和IsFull对堆栈进行排序。 IsEmpty =！IsFull。 因此，您要求使用Top和IsEmpty对堆栈进行排序。
对于糟糕的你不能有另外两个堆叠，那么你可以在O（n）空间玩过河内的塔 。
//一个java版本
public static void sort(Stack s){ if(s.size() > 0){ int tmp = s.pop(); sort(s); sortFromBottom(s, tmp); } } private static void sortFromBottom(Stack s, Integer value){ if(s.size() == 0){ s.add(value); }else{ int tmpValue = s.peek(); if(tmpValue < value){ s.pop(); sortFromBottom(s, value); s.push(tmpValue); }else{ s.push(value); } } }
/** * Sort the stack using only Stack API, without using other data structure * Ascending from bottom to top */ public class SortStack> { int sorted; /** * Just Bubble Sort. */ private void bubble(Stack s, T max) { if (s.empty() || s.size() == sorted) { s.push(max); sorted++; return; // note return } T currentTop = s.pop(); if (max.compareTo(currentTop) < 0) { T tmp = max; max = currentTop; currentTop = tmp; } bubble(s, max); s.push(currentTop); } public Stack sortAscending(Stack s) { sorted = 0; if (s == null || s.size() <= 1) { return s; } while (sorted != s.size()) { bubble(s, s.pop()); } return s; } /** * Just Insert Sort. */ private void insertSort(Stack s) { if (s.empty()) { return; } T currentTop = s.pop(); insertSort(s); insert(s, currentTop); } private void insert(Stack s, T insert) { if (s.isEmpty() || insert.compareTo(s.peek()) <= 0) { s.push(insert); return; } T current = s.pop(); insert(s, insert); s.push(current); } public Stack sortAscendingByInsertSort(Stack s) { if (s == null || s.size() <= 1) { return s; } insertSort(s); return s; } }
没有额外空间的堆栈排序是不可能的。 至少没有达到理智的心态。 我们肯定可以在这里使用递归堆栈作为额外空间。 以下方法可能很有帮助。
我的方法是O（N ** 2）。 在这里，我每次迭代堆栈N次，每次都在堆栈中修复第i个元素。
首先通过弹出N个元素并按下min_element来修复底部元素，然后在第二个尝试中通过弹出N-1个元素来固定第二个元素，然后按下除了之前推送的min_element，依此类推。
有关详细信息，请参阅以下代码。
stack stk; int sort_util(stack &stk,int n,int mn) { if(n==0) { stk.push(mn); return mn; } int vl = stk.top(); stk.pop(); int fmin = sort_util(stk,n-1,min(mn,vl)); if(fmin==vl) return INT_MAX; else stk.push(vl); return fmin; } void sort_stack(stack &stk) { for(int i=stk.size();i>1;i--) sort_util(stk,i,stk.top()); }