如何仅使用堆栈操作对堆栈进行排序？
我在网上发现了这个问题。
给定堆栈S，编写C程序以对堆栈进行排序（按升序排列）。 我们不允许对堆栈的实现方式做任何假设。 唯一要使用的function是：
Push Pop Top IsEmpty IsFull 我想我们可以构建堆并对其进行排序。 什么是最佳解决方案？
假设这里允许的唯一数据结构是Stack，那么你可以使用2个Stacks。
迭代直到原始堆栈为空并且在每次迭代中，从原始堆栈弹出元素，而第二个堆栈中的顶部元素大于移除的元素，弹出第二个堆栈并将其推送到原始堆栈。 现在，您可以将最初从原始堆栈弹出的元素推送到第二个堆栈。
该方法的时间复杂度为O（N ^ 2）。
用于实现此算法的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)); } }
给定这些堆栈操作，您可以编写递归插入排序。
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); } }
它可以使用相同的堆栈递归完成。 O（n ^ 2）我用C ++编写了它，但转换为C是微不足道的。 我只是喜欢模板，你确实用C ++标记了你的问题
template void Insert(const T& element, Stack& stack) { if(element > stack.Top()) { T top = stack.Pop(); Insert(element, stack); stack.Push(top); } else { stack.Push(element); } } template void StackSort(Stack& stack) { if(!stack.IsEmpty()) { T top = stack.Pop(); StackSort(stack); Insert(top, stack); } }
编辑得到我的投票！ :)）
煎饼排序是另一种有趣的方式： http ： //en.wikipedia.org/wiki/Pancake_sorting#cite_note-4 。
来自T33C答案的修改代码
（在Svante将语言标签从c ++改为c之前给出 ）：
stack.top()只能检查!stack.empty()
void insert(int element, stack &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 & stack) { if (!stack.empty()) { int top = stack.top(); stack.pop(); sortStack(stack); insert(top, stack); } }
3堆栈排序使用多相合并排序
这应该是实现3堆栈排序的最快方法。 目标是在从已排序的堆栈中弹出项目时以最新的序列结束。
用于多相合并排序的Wiki文章（使用数组）：
http://en.wikipedia.org/wiki/Polyphase_merge_sort
示例C ++代码，用于3个堆栈多阶段排序，使用指针，指针作为每个堆栈的堆栈指针，以及指向每个运行结束和每个堆栈结束的指针。 运行大小指针用于跟踪运行大小何时递增或递减堆栈中间。 降序序列标志用于跟踪序列在堆栈之间传输数据时是下降还是上升。 它在开始时初始化，然后在每对运行合并后交替。
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 }
使用包含交换函数的自定义堆栈类（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 }
如果你没有关于堆栈内容的任何额外信息，那么你几乎不会把所有的数据拿出来，排序，然后把它重新放进去.Hepport在这里会很棒，就像quicksort或introsort一样。
如果对使用其他数据结构没有限制，我会说最小堆。 每当从堆栈中弹出一个元素时，都会放入堆中。 弹出完成后，从堆顶部取出元素（其余部分最少）并将其推入堆栈。 重复此过程直到堆为空。
为了创建堆，平均时间是O（nlogn）; 为了从堆中删除元素并按升序放回元素，平均时间也是O（nlogn）。
它看起来怎么样？
请注意， Michael J. Barber的答案（见上文）是不正确的，它会在空元素时忘记将元素推回堆栈。 正确的版本如下：
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); // !!! must step, otherwise, the stack will eventually be empty after sorting !!! } }
以下是基于@OrenD给出的答案的Javascript解决方案
var org = [4,67,2,9,5,11,3]; var helper = []; while(org.length > 0){ var temp = org.pop(); while((helper.length > 0) && (helper[helper.length-1] < temp)){ org.push(helper.pop()); } helper.push(temp); } while(helper.length > 0){ org.push(helper.pop()); }
三堆的游戏
使用三个堆栈S（源堆栈，带有未排序元素的堆栈），A，B，您可以开始玩类似于合并排序的游戏。
我认为很明显，如果你在A和B上排序了元素（在同一个方向，既有升序也有降序），你可以使用S合并排序A和B，然后将结果移动到，例如，B 。
你在A，B或S上有一些元素这一事实并不能阻止你使用A，B或S进行合并（只要你有A，B和S当前大小的标记，那么你不会超调）。 如果你的程序在S上带有有序元素，那么使用A和B将你排序的部分从你想要的任何方向移除到A或B都不是大脑：你可以将它以相反的顺序直接放到A或B，或者，例如，将所有元素放置到A，然后再将其反转到B.
假设您在A上有4个排序元素，在B上有16个元素，在S上有一些未排序元素。
A.push（S.pop）现在创建一个2元素的排序合并。 再次B.push（S.pop）并创建另一个2元素排序合并。 如果合并没有分开和/或不在同一方向，您可以按照自己喜欢的方式操作元素，直到在B（或甚至S）上达到4元素排序合并。 现在合并来自A的初始4元素排序合并和B上的那个部分，直到达到8元素排序合并。
您重复所有内容，直到您创建另一个8元素排序合并。 您按顺序将其放在B（或S）上并合并以获得16个元素的排序合并。 现在你把它放在A（或S）上并与我们在B上一直有的16元素合并合并。
优化的实现很棘手，因为您需要减少从一个堆栈到另一个堆栈的移动（恢复）排序合并。 但是，如果您修复并决定要使用A，B和S，并强制使用例如：A按降序包含较小和B较大的合并部分，则算法更简单。
您需要将一些顶部元素从一个堆栈移动到另一个堆栈的事实是为复杂性添加一个常数因子，但它永远不会超过2.除此之外，复杂性是n * log（n）（达到2n元素）通过合并2个n元素排序合并来排序合并，合并所需的步骤不超过2n。）
用C＃实现（其他类似语言很明显）
void Stacking(Stack sourceStack, Stack mainStack, Stack childStack, int n) { if (n == 0) return; if (n == 1) { mainStack.Push(sourceStack.Pop()); return; } int mainSize = n/2; int childSize = n - n/2; Stacking(sourceStack, mainStack, childStack, mainSize); Stacking(sourceStack, childStack, mainStack, childSize); while (true) { while (mainSize > 0 && mainStack.Peek() >= childStack.Peek()) { sourceStack.Push(mainStack.Pop()); mainSize--; } if (mainSize == 0) break; while (childSize > 0 && childStack.Peek() >= mainStack.Peek()) { sourceStack.Push(childStack.Pop()); childSize--; } if (childSize == 0) break; } while (mainSize > 0) { sourceStack.Push(mainStack.Pop()); mainSize--; } while (childSize > 0) { sourceStack.Push(childStack.Pop()); childSize--; } for (int i = 0; i < n; i++) mainStack.Push(sourceStack.Pop()); } void SortStack(Stack sourceStack) { int n = sourceStack.Count(); // possible optimization: if (n < 2) return; Stack mainStack = new Stack (); Stack childStack = new Stack (); Stacking(sourceStack, mainStack, childStack, n); for (int i = 0; i < n; i++) sourceStack.Push(mainStack.Pop()); }
log（n）堆栈的游戏
如果允许最多使用log（n）堆栈，则可以简化上述过程。 这个堆栈数并不意味着您将使用大于n的额外空间。 您只需标记将用于合并1,2,4 ...元素的堆栈。 在这种情况下，您不关心顺序，因为合并2 ^ n的部分将始终按相同方向排序。 但是，这个解决方案只是规避了你只能使用推送和弹出操作的事实; 除此之外，它相当于所有方面的合并排序。 实质上，如果堆栈数量不受限制，那么您也可以轻松模拟快速排序。
/* the basic idea is we go on * popping one element (o) from the original stack (s) and we * compare it with the new stack (temp) * if o (the popped element from original stack) * is < the peek element from new stack temp * then we push the new stack element to original stack * and recursively keep calling till temp is not empty * and then push the element at the right place. * else we push the element to the new stack temp * (o >= new temp stack. * * Entire logic is recursive. */ public void sortstk( Stack s ) { Stack temp = new Stack (); while( !s.isEmpty() ) { int s1 = (int) s.pop(); while( !temp.isEmpty() && (temp.peek() > s1) ) { s.push( temp.pop() ); } temp.push( s1 ); } // Print the entire sorted stack from temp stack for( int i = 0; i < temp.size(); i++ ) { System.out.println( temp.elementAt( i ) ); } }
我认为冒泡排序可以在递归的堆栈上工作。
void sortStack(stack& 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 & 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); }