C语言 如何仅使用 Push、Pop、Top、IsEmpty、IsFull 对堆栈进行排序？
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/2168803/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
How to sort a stack using only Push, Pop, Top, IsEmpty, IsFull?
提问by AJ.
Given a stack S, need to sort the stack using only Push, Pop, Top, IsEmpty, IsFull.
给定一个堆栈 S，只需要使用Push、Pop、Top、IsEmpty、对堆栈进行排序IsFull。
Looking for most simple solution.
寻找最简单的解决方案。
Edited: Removed in place condition. Can't use another stack or queue.
已编辑：原地移除。不能使用另一个堆栈或队列。
回答by SiLent SoNG
For this problem, can we consider using system stack? Make several recursive calls.
对于这个问题，可以考虑使用系统栈吗？进行多次递归调用。
public static void sort(Stack<Integer> s) {
if (!s.isEmpty()) {
Integer t = s.pop();
sort(s);
insert(t, s);
}
}
private static void insert(Integer x, Stack<Integer> 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);
}
}
回答by DigitalRoss
It can be done...
可以办到...
Ok: sorted, ahem, "in-place" with only the listed ops, didn't need Top() or IsFull() or another stack or data structure other than the call frames. (Presumably the whole point of the homeworkproblem was to require a recursive solution.)
好的：排序，咳咳，“就地”仅使用列出的操作，不需要 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]
回答by Anthony Forloney
techInterview Discussion - Sorting on Stack
More pseudo than anything, but there is code examples and possible solution.
比任何东西都更伪，但有代码示例和可能的解决方案。
回答by George
Its not possible.
这是不可能的。
That happens because you cant iterate through the stack, because it has to be in place (you could if you would use extra memory). So if you cant iterate through the stack you cant even compare two elements of the stack. A sort without comparing would need extra memory, so that cant be used either.
发生这种情况是因为您无法遍历堆栈，因为它必须就位（如果您使用额外的内存，则可以）。因此，如果您无法遍历堆栈，您甚至无法比较堆栈的两个元素。没有比较的排序需要额外的内存，因此也不能使用。
Also im sure its not homework, because i dont think a teacher would give you a problem that cant be solved.
我也确定它不是家庭作业，因为我不认为老师会给你一个无法解决的问题。
If you really have to do it only with stacks, just use 1-2 extra temporary stacks (i think 2 are needed, but not 100% sure) and do it.
如果你真的只需要用堆栈来做，只需使用 1-2 个额外的临时堆栈（我认为需要 2 个，但不是 100% 确定）并执行它。
回答by SF.
What temporary data structures can you use? With push and pop, and no temporary storage for nelements, accessing data near the bottom of the stack would be impossible without storing the rest -somewhere-.
您可以使用哪些临时数据结构？使用 push 和 pop，并且没有n 个元素的临时存储，访问堆栈底部附近的数据是不可能的，除非将其余的存储在某处。
If top(equiv to {x=pop();push(x);return x}) was replaced with shift, it would be perfectly doable - the stack would change into fifo (shift+push; pop would fall into disuse) and it would allow for an easy bubblesort on currently available elements.
如果top(相当于{x=pop();push(x);return x}) 被替换为shift，这将是完全可行的 - 堆栈将更改为 fifo（shift+push；pop 将被废弃），并且它将允许对当前可用元素进行简单的冒泡排序。
回答by Chris H
You can't. You can't reorder the contents of a stack without removing elements, by definition. Also push and pop aren't in-place operations, so basically you're asking to sort a stack with Top, IsEmpty and IsFull. IsEmpty = !IsFull. So you're asking to sort a stack with Top and IsEmpty.
你不能。根据定义，您不能在不删除元素的情况下重新排序堆栈的内容。push 和 pop 也不是就地操作，所以基本上你要求使用 Top、IsEmpty 和 IsFull 对堆栈进行排序。IsEmpty = !IsFull。因此，您要求使用 Top 和 IsEmpty 对堆栈进行排序。
回答by Albin Sunnanbo
To bad you couldn't have two other stacks, then you could have played the Towers of Hanoiin O(n) space.
糟糕的是你不能有另外两个筹码，那么你可以在 O(n) 空间玩河内塔。
回答by Jiaji Li
//A java version
//一个java版本
public static void sort(Stack<Integer> s){
if(s.size() > 0){
int tmp = s.pop();
sort(s);
sortFromBottom(s, tmp);
}
}
private static void sortFromBottom(Stack<Integer> 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);
}
}
}
回答by Bruce Zu
Bubble Sort and Insert Sort in Java https://github.com/BruceZu/sawdust/blob/82ef4729ee9d2de50fdceab2c8976d00f2fd3ba0/dataStructuresAndAlgorithms/src/main/java/stack/SortStack.java
Java 中的冒泡排序和插入排序 https://github.com/BruceZu/sawdust/blob/82ef4729ee9d2de50fdceab2c8976d00f2fd3ba0/dataStructuresAndAlgorithms/src/main/java/stack/SortStack.java
/**
* Sort the stack using only Stack API, without using other data structure
* Ascending from bottom to top
*/
public class SortStack<T extends Comparable<T>> {
int sorted;
/**
* Just Bubble Sort.
*/
private void bubble(Stack<T> 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<T> sortAscending(Stack<T> 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<T> s) {
if (s.empty()) {
return;
}
T currentTop = s.pop();
insertSort(s);
insert(s, currentTop);
}
private void insert(Stack<T> 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<T> sortAscendingByInsertSort(Stack<T> s) {
if (s == null || s.size() <= 1) {
return s;
}
insertSort(s);
return s;
}
}
回答by dhruvsharma
Sorting a stack without extra space is quite not a possibility . At least not coming to my sane mind . We can surely use the recursion stack as extra space over here . The below approach might be helful .
在没有额外空间的情况下对堆栈进行排序是不可能的。至少在我理智的情况下不会。我们当然可以使用递归堆栈作为这里的额外空间。下面的方法可能很有帮助。
My approach is O(N**2) . Over here I am iterating over stack N times, every time fixing the ith element in the stack .
我的方法是 O(N**2) 。在这里，我迭代堆栈 N 次，每次修复堆栈中的第 i 个元素。
Firstly fixed the bottom element by popping out N elements and pushing min_element and in Second try fixed the 2nd element from bottom by popping out N-1 elements and pushing min_element except the one pushed before this And so on .
首先通过弹出 N 个元素并推送 min_element 来固定底部元素，然后在第二次尝试通过弹出 N-1 个元素并推送 min_element 来固定底部的第二个元素，除了在此之前推送的那个之外，依此类推。
Refer to the code below for more details .
有关详细信息，请参阅下面的代码。
stack<int> stk;
int sort_util(stack<int> &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<int> &stk)
{
for(int i=stk.size();i>1;i--)
sort_util(stk,i,stk.top());
}
