C语言 如何仅使用堆栈操作对堆栈进行排序？
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/4826311/
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 stack operations?
提问by Michael J. Barber
I found this question on the web.
我在网上找到了这个问题。
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:
给定一个堆栈 S，编写一个 C 程序来对堆栈进行排序（按升序）。我们不允许对堆栈的实现方式做出任何假设。要使用的唯一功能是：
Push
Pop
Top
IsEmpty
IsFull
I think we can build heap and sort it. What is optimal solution to this?
我认为我们可以构建堆并对其进行排序。对此的最佳解决方案是什么？
回答by OrenD
Assuming that the only data structure allowed here is the Stack, then you could use 2 Stacks.
假设这里允许的唯一数据结构是堆栈，那么您可以使用 2 个堆栈。
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.
迭代直到原栈为空，在每次迭代中，从原栈中弹出一个元素，当第二个栈顶元素大于移除的元素时，弹出第二个栈并将其压入原栈。现在您可以将最初从原始堆栈中弹出的元素推送到第二个堆栈。
The time complexity of this approach is O(N^2).
这种方法的时间复杂度是 O(N^2)。
C code to implement this algorithm would be (excuse my rusty C skills):
实现这个算法的 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));
}
}
回答by Michael J. Barber
Given those stack operations, you could write a recursive insertion sort.
鉴于这些堆栈操作，您可以编写递归插入排序。
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);
}
}
回答by T33C
It can be done recursively using the same stack. O(n^2) I have coded it in C++ but the conversion to C is trivial. I just like templates and you did tag your question as C++
它可以使用相同的堆栈递归完成。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);
}
}
Edited to get my vote back! :))
编辑以收回我的投票！:))
回答by Kakira
Pancake sort is another interesting way to do this: http://en.wikipedia.org/wiki/Pancake_sorting#cite_note-4.
Pancake sort 是另一种有趣的方法：http: //en.wikipedia.org/wiki/Pancake_sorting#cite_note-4。
回答by rcgldr
3 stack sort using polyphase merge sort
3 堆栈排序使用多相归并排序
This should be the fastest way to implement a 3 stack sort. Time complexity is O(n log(n)). The goal is to end up with an ascending sequence as items are popped from a sorted stack.
这应该是实现 3 堆栈排序的最快方法。时间复杂度为 O(n log(n))。目标是在项目从排序堆栈中弹出时以升序结束。
Wiki article for polyphase merge sort (using arrays):
多相归并排序的 Wiki 文章（使用数组）：
http://en.wikipedia.org/wiki/Polyphase_merge_sort
http://en.wikipedia.org/wiki/Polyphase_merge_sort
Example C++ code for 3 stack polyphase sort, using pointers, a pointer as a stack pointer for each stack, and a pointer to the end of each run and the end of each stack. The run size pointer is used to keep track of when the run size increments or decrements mid stack. A descending sequence flag is used to keep track if sequences are descending or ascending as data is transferred between stacks. It is initialized at the start, and then alternates after every pair of runs is merged.
3 堆栈多相排序的示例 C++ 代码，使用指针，一个指针作为每个堆栈的堆栈指针，以及一个指向每次运行结束和每个堆栈结束的指针。运行大小指针用于跟踪运行大小何时在堆栈中间增加或减少。当数据在堆栈之间传输时，降序序列标志用于跟踪序列是降序还是升序。它在开始时被初始化，然后在每对运行合并后交替。
typedef unsigned int uint32_t;
static size_t fibtbl[48] =
{ 0, 1, 1, 2, 3, 5,
8, 13, 21, 34, 55, 89,
144, 233, 377, 610, 987, 1597,
2584, 4181, 6765, 10946, 17711, 28657,
46368, 75025, 121393, 196418, 317811, 514229,
832040, 1346269, 2178309, 3524578, 5702887, 9227465,
14930352, 24157817, 39088169, 63245986, 102334155, 165580141,
267914296, 433494437, 701408733,1134903170,1836311903,2971215073};
// binary search: return index of largest fib() <= n
size_t flfib(size_t n)
{
size_t lo = 0;
size_t hi = sizeof(fibtbl)/sizeof(fibtbl[0]);
while((hi - lo) > 1){
size_t i = (lo + hi)/2;
if(n < fibtbl[i]){
hi = i;
continue;
}
if(n > fibtbl[i]){
lo = i;
continue;
}
return i;
}
return lo;
}
// poly phase merge sort array using 3 arrays as stacks, a is source
uint32_t * ppmrg3s(uint32_t a[], uint32_t b[], uint32_t c[], size_t n)
{
if(n < 2)
return a+n;
uint32_t *asp = a; // a stack ptr
uint32_t *aer; // a end run
uint32_t *aes = a + n; // a end
uint32_t *bsp = b + n; // b stack ptr
uint32_t *ber; // b end run
uint32_t *bes = b + n; // b end
uint32_t *csp = c + n; // c stack ptr
uint32_t *ces = c + n; // c end
uint32_t *rsp = 0; // run size change stack ptr
size_t ars = 1; // run sizes
size_t brs = 1;
size_t scv = 0-1; // size change increment / decrement
bool dsf; // == 1 if descending sequence
{ // block for local variable scope
size_t f = flfib(n); // fibtbl[f+1] > n >= fibtbl[f]
dsf = ((f%3) == 0); // init compare flag
if(fibtbl[f] == n){ // if exact fibonacci size, move to b
for(size_t i = 0; i < fibtbl[f-1]; i++)
*(--bsp) = *(asp++);
} else { // else move to b, c
// update compare flag
dsf ^= (n - fibtbl[f]) & 1;
// move excess elements to b
aer = a + n - fibtbl[f];
while (asp < aer)
*(--bsp) = *(asp++);
// move dummy count elements to c
aer = a + fibtbl[f - 1];
while (asp < aer)
*(--csp) = *(asp++);
rsp = csp; // set run size change ptr
}
} // end local variable block
while(1){ // setup to merge pair of runs
if(asp == rsp){ // check for size count change
ars += scv; // (due to dummy run size == 0)
scv = 0-scv;
rsp = csp;
}
if(bsp == rsp){
brs += scv;
scv = 0-scv;
rsp = csp;
}
aer = asp + ars; // init end run ptrs
ber = bsp + brs;
while(1){ // merging pair of runs
if(dsf ^ (*asp <= *bsp)){ // if a <= b
*(--csp) = *(asp++); // move a to c
if(asp != aer) // if not end a run
continue; // continue back to compare
do // else move rest of b run to c
*(--csp) = *(bsp++);
while (bsp < ber);
break; // and break
} else { // else a > b
*(--csp) = *(bsp++); // move b to c
if(bsp != ber) // if not end b run
continue; // continue back to compare
do // else move rest of a run to c
*(--csp) = *(asp++);
while (asp < aer);
break; // and break
}
} // end merging pair of runs
dsf ^= 1; // toggle compare flag
if(bsp == bes){ // if b empty
if(asp == aes) // if a empty, done
break;
std::swap(bsp, csp); // swap b, c
std::swap(bes, ces);
brs += ars; // update run size
} else { // else b not empty
if(asp != aes) // if a not empty
continue; // continue back to setup next merge
std::swap(asp, csp); // swap a, c
std::swap(aes, ces);
ars += brs; // update run size
}
}
return csp; // return ptr to sorted array
}
Example java code for sorting using a custom stack class (xstack) that includes a swap function.
使用包含交换函数的自定义堆栈类 (xstack) 进行排序的示例 Java 代码。
static final int[] FIBTBL =
{ 0, 1, 1, 2, 3, 5,
8, 13, 21, 34, 55, 89,
144, 233, 377, 610, 987, 1597,
2584, 4181, 6765, 10946, 17711, 28657,
46368, 75025, 121393, 196418, 317811, 514229,
832040, 1346269, 2178309, 3524578, 5702887, 9227465,
14930352, 24157817, 39088169, 63245986, 102334155, 165580141,
267914296, 433494437, 701408733,1134903170,1836311903};
// return index of largest fib() <= n
static int flfib(int n)
{
int lo = 0;
int hi = 47;
while((hi - lo) > 1){
int i = (lo + hi)/2;
if(n < FIBTBL[i]){
hi = i;
continue;
}
if(n > FIBTBL[i]){
lo = i;
continue;
}
return i;
}
return lo;
}
// poly phase merge sort using 3 stacks
static void ppmrg3s(xstack a, xstack b, xstack c)
{
if(a.size() < 2)
return;
int ars = 1; // init run sizes
int brs = 1;
int asc = 0; // no size change
int bsc = 0;
int csc = 0;
int scv = 0-1; // size change value
boolean dsf; // == 1 if descending sequence
{ // block for local variable scope
int f = flfib(a.size()); // FIBTBL[f+1] > size >= FIBTBL[f]
dsf = ((f%3) == 0); // init compare flag
if(FIBTBL[f] == a.size()){ // if exact fibonacci size,
for (int i = 0; i < FIBTBL[f - 1]; i++) { // move to b
b.push(a.pop());
}
} else { // else move to b, c
// update compare flag
dsf ^= 1 == ((a.size() - FIBTBL[f]) & 1);
// i = excess run count
int i = a.size() - FIBTBL[f];
// j = dummy run count
int j = FIBTBL[f + 1] - a.size();
// move excess elements to b
do{
b.push(a.pop());
}while(0 != --i);
// move dummy count elements to c
do{
c.push(a.pop());
}while(0 != --j);
csc = c.size();
}
} // end block
while(true){ // setup to merge pair of runs
if(asc == a.size()){ // check for size count change
ars += scv; // (due to dummy run size == 0)
scv = 0-scv;
asc = 0;
csc = c.size();
}
if(bsc == b.size()){
brs += scv;
scv = 0-scv;
bsc = 0;
csc = c.size();
}
int arc = ars; // init run counters
int brc = brs;
while(true){ // merging pair of runs
if(dsf ^ (a.peek() <= b.peek())){
c.push(a.pop()); // move a to c
if(--arc != 0) // if not end a
continue; // continue back to compare
do{ // else move rest of b run to c
c.push(b.pop());
}while(0 != --brc);
break; // and break
} else {
c.push(b.pop()); // move b to c
if(0 != --brc) // if not end b
continue; // continue back to compare
do{ // else move rest of a run to c
c.push(a.pop());
}while(0 != --arc);
break; // and break
}
} // end merging pair of runs
dsf ^= true; // toggle compare flag
if(b.empty()){ // if end b
if(a.empty()) // if end a, done
break;
b.swap(c); // swap b, c
brs += ars;
if (0 == asc)
bsc = csc;
} else { // else not end b
if(!a.empty()) // if not end a
continue; // continue back to setup next merge
a.swap(c); // swap a, c
ars += brs;
if (0 == bsc)
asc = csc;
}
}
a.swap(c); // return sorted stack in a
}
The java custom stack class:
java自定义堆栈类：
class xstack{
int []ar; // array
int sz; // size
int sp; // stack pointer
public xstack(int sz){ // constructor with size
this.ar = new int[sz];
this.sz = sz;
this.sp = sz;
}
public void push(int d){
this.ar[--sp] = d;
}
public int pop(){
return this.ar[sp++];
}
public int peek(){
return this.ar[sp];
}
public boolean empty(){
return sp == sz;
}
public int size(){
return sz-sp;
}
public void swap(xstack othr){
int []tempar = othr.ar;
int tempsz = othr.sz;
int tempsp = othr.sp;
othr.ar = this.ar;
othr.sz = this.sz;
othr.sp = this.sp;
this.ar = tempar;
this.sz = tempsz;
this.sp = tempsp;
}
}
回答by B.W
Modified code from T33C's answer
(given before Svante corrected the language tag from c++to c):stack.top()can only be checked if !stack.empty()
从修改后的代码T33C的答案
（因为斯万修正从语言标记之前C ++到Ç）：stack.top()只能如果选中!stack.empty()
void insert(int element, stack<int> &stack) {
if (!stack.empty() && element > stack.top()) {
int top = stack.top();
stack.pop();
insert(element, stack);
stack.push(top);
}
else {
stack.push(element);
}
}
void sortStack(stack<int> & stack) {
if (!stack.empty()) {
int top = stack.top();
stack.pop();
sortStack(stack);
insert(top, stack);
}
}
回答by chaosMonkey
I think that the bubble sort could work on the stack with recursion.
我认为冒泡排序可以通过递归在堆栈上工作。
void sortStack(stack<int>& st){
bool flag = true;
int n = st.size();
for(int i = 1; i <= n - 1 && flag; i++){
flag = false;
bubbleSortStack(st, flag, i);
}
}
void bubbleSortStack(stack<int>& st, bool& flag, int endSize){
if(st.size() == endSize)
return;
int val = st.top();
st.pop();
if(val > st.top()){
flag = true;
int tmp = st.top();
st.push(val);
val = tmp;
}
bubbleSortStack(st, flag);
st.push(val);
}
回答by Rock
class Program
{
static void Main(string[] args)
{
Stack<int> stack = new Stack<int>();
stack.Push(8);
stack.Push(5);
stack.Push(3);
stack.Push(4);
stack.Push(7);
stack.Push(9);
stack.Push(5);
stack.Push(6);
Stack<int> tempStack = new Stack<int>();
while (stack.Count > 0)
{
int temp = stack.Pop();
while(tempStack.Count>0 && tempStack.Peek() > temp)
{
stack.Push(tempStack.Pop());
}
tempStack.Push(temp);
}
while (tempStack.Count > 0)
{
Console.Write(tempStack.Pop() + " ");
}
Console.ReadLine();
}
}
回答by Aayush Anand
Since nothing is said about how many extra stacks can be used, so I am assuming any number of stacks can be used to solve the sorting problem as efficiently as possible.
由于没有说明可以使用多少个额外的堆栈，所以我假设可以使用任意数量的堆栈来尽可能有效地解决排序问题。
If you forget about stack constraint for now and assume this was a normal sorting problem. Then how can you solve it? (Hint: Merge sort)
如果您暂时忘记堆栈约束并假设这是一个正常的排序问题。那你怎么解决呢？（提示：归并排序）
Perform normal merge sort on the stack using auxiliary stacks. Time complexity - N*log(n).
使用辅助堆栈对堆栈执行正常归并排序。时间复杂度 - N*log(n)。
回答by templatetypedef
If you don't have any extra information about the stack contents, then you pretty much are stuck just taking all the data out, sorting it, and putting it back in. Heapsort would be great here, as would quicksort or introsort.
如果您没有关于堆栈内容的任何额外信息，那么您几乎只能将所有数据取出、排序并放回原处。Heapsort 在这里会很棒，quicksort 或 introsort 也是如此。
