本文概述

• C ++
• C
• Java
• Python3
• C#

给定一个栈, 使用递归对其进行排序。不允许使用while, for..etc等任何循环结构。我们只能在Stack S上使用以下ADT函数：

is_empty(S): Tests whether stack is empty or not. push(S): Adds new element to the stack. pop(S): Removes top element from the stack. top(S): Returns value of the top element. Note that this function does not remove element from the stack.

例子：

Input:-3< --- Top 14 18 -5 30 Output: 30< --- Top 18 14 -3 -5

这个问题主要是使用递归的反向栈的一种变体。
解决方案的想法是将所有值保留在函数调用栈中, 直到栈变空。当栈变空时, 请按排序顺序一次插入所有保留的项目。在这里, 排序顺序很重要。
算法
我们可以使用以下算法对栈元素进行排序：

sortStack(stack S) if stack is not empty: temp = pop(S); sortStack(S); sortedInsert(S, temp);

下面的算法是对元素进行插入排序：

sortedInsert(Stack S, element) if stack is empty OR element > top element push(S, elem) else temp = pop(S) sortedInsert(S, element) push(S, temp)

插图： 

Let given stack be -3< -- top of the stack 14 18 -5 30

让我们使用上面的示例来说明栈的排序：
首先从栈中弹出所有元素, 然后将弹出的元素存储在变量" temp"中。弹出所有elements函数后, 其栈框架将如下所示：

temp = -3--> stack frame #1 temp = 14--> stack frame #2 temp = 18--> stack frame #3 temp = -5--> stack frame #4 temp = 30--> stack frame #5

现在栈为空, 并调用了" insert_in_sorted_order()"函数, 并在栈底部插入了30(从栈帧5开始)。现在栈如下所示：

30< -- top of the stack

现在选择下一个元素, 即-5(来自栈帧＃4)。由于-5 < 30, 因此-5会插入栈的底部。现在栈变为：

30< -- top of the stack -0

接下来的18个(来自栈帧3)被选中。由于18 < 30, 因此将18插入30以下。现在栈变为：

30< -- top of the stack 18 -5

接下来的14个(来自栈帧2)被选中。由于14 < 30和14 < 18, 因此将其插入18以下。现在, 栈变为：

30< -- top of the stack 18 14 -5

现在, 选择-3(从栈帧1), 因为-3 < 30和-3 < 18和-3 < 14, 它将插入14以下。现在, 栈变为：

30< -- top of the stack 18 14 -3 -5

实现
下面是上述算法的实现。
C ++

// C++ program to sort a stack using recursion #include < iostream> using namespace std; // Stack is represented using linked list struct stack { int data; struct stack* next; }; // Utility function to initialize stack void initStack( struct stack** s) { *s = NULL; }// Utility function to chcek if stack is empty int isEmpty( struct stack* s) { if (s == NULL) return 1; return 0; }// Utility function to push an item to stack void push( struct stack** s, int x) { struct stack* p = ( struct stack*) malloc ( sizeof (*p)); if (p == NULL) { fprintf (stderr, "Memory allocation failed.\n" ); return ; }p-> data = https://www.lsbin.com/x; p-> next = *s; *s = p; }// Utility function to remove an item from stack int pop( struct stack** s) { int x; struct stack* temp; x = (*s)-> data; temp = *s; (*s) = (*s)-> next; free (temp); return x; }// Function to find top item int top( struct stack* s) { return (s-> data); }// Recursive function to insert an item x in sorted way void sortedInsert( struct stack** s, int x) { // Base case: Either stack is empty or newly inserted // item is greater than top (more than all existing) if (isEmpty(*s) or x > top(*s)) { push(s, x); return ; }// If top is greater, remove the top item and recur int temp = pop(s); sortedInsert(s, x); // Put back the top item removed earlier push(s, temp); }// Function to sort stack void sortStack( struct stack** s) { // If stack is not empty if (!isEmpty(*s)) { // Remove the top item int x = pop(s); // Sort remaining stack sortStack(s); // Push the top item back in sorted stack sortedInsert(s, x); } }// Utility function to print contents of stack void printStack( struct stack* s) { while (s) { cout < < s-> data < <" " ; s = s-> next; } cout < < "\n" ; }// Driver code int main( void ) { struct stack* top; initStack(& top); push(& top, 30); push(& top, -5); push(& top, 18); push(& top, 14); push(& top, -3); cout < < "Stack elements before sorting:\n" ; printStack(top); sortStack(& top); cout < < "\n" ; cout < < "Stack elements after sorting:\n" ; printStack(top); return 0; }// This code is contributed by SHUBHAMSINGH10

C

// C program to sort a stack using recursion #include < stdio.h> #include < stdlib.h> // Stack is represented using linked list struct stack { int data; struct stack* next; }; // Utility function to initialize stack void initStack( struct stack** s) { *s = NULL; }// Utility function to chcek if stack is empty int isEmpty( struct stack* s) { if (s == NULL) return 1; return 0; }// Utility function to push an item to stack void push( struct stack** s, int x) { struct stack* p = ( struct stack*) malloc ( sizeof (*p)); if (p == NULL) { fprintf (stderr, "Memory allocation failed.\n" ); return ; }p-> data = https://www.lsbin.com/x; p-> next = *s; *s = p; }// Utility function to remove an item from stack int pop( struct stack** s) { int x; struct stack* temp; x = (*s)-> data; temp = *s; (*s) = (*s)-> next; free (temp); return x; }// Function to find top item int top( struct stack* s) { return (s-> data); }// Recursive function to insert an item x in sorted way void sortedInsert( struct stack** s, int x) { // Base case: Either stack is empty or newly inserted // item is greater than top (more than all existing) if (isEmpty(*s) || x > top(*s)) { push(s, x); return ; }// If top is greater, remove the top item and recur int temp = pop(s); sortedInsert(s, x); // Put back the top item removed earlier push(s, temp); }// Function to sort stack void sortStack( struct stack** s) { // If stack is not empty if (!isEmpty(*s)) { // Remove the top item int x = pop(s); // Sort remaining stack sortStack(s); // Push the top item back in sorted stack sortedInsert(s, x); } }// Utility function to print contents of stack void printStack( struct stack* s) { while (s) { printf ("%d " , s-> data); s = s-> next; } printf ( "\n" ); }// Driver code int main( void ) { struct stack* top; initStack(& top); push(& top, 30); push(& top, -5); push(& top, 18); push(& top, 14); push(& top, -3); printf ( "Stack elements before sorting:\n" ); printStack(top); sortStack(& top); printf ( "\n\n" ); printf ( "Stack elements after sorting:\n" ); printStack(top); return 0; }

Java

// Java program to sort a Stack using recursion // Note that here predefined Stack class is used // for stack operationimport java.util.ListIterator; import java.util.Stack; class Test { // Recursive Method to insert an item x in sorted way static void sortedInsert(Stack< Integer> s, int x) { // Base case: Either stack is empty or newly // inserted item is greater than top (more than all // existing) if (s.isEmpty() || x > s.peek()) { s.push(x); return ; }// If top is greater, remove the top item and recur int temp = s.pop(); sortedInsert(s, x); // Put back the top item removed earlier s.push(temp); }// Method to sort stack static void sortStack(Stack< Integer> s) { // If stack is not empty if (!s.isEmpty()) { // Remove the top item int x = s.pop(); // Sort remaining stack sortStack(s); // Push the top item back in sorted stack sortedInsert(s, x); } }// Utility Method to print contents of stack static void printStack(Stack< Integer> s) { ListIterator< Integer> lt = s.listIterator(); // forwarding while (lt.hasNext()) lt.next(); // printing from top to bottom while (lt.hasPrevious()) System.out.print(lt.previous() + " " ); }// Driver code public static void main(String[] args) { Stack< Integer> s = new Stack< > (); s.push( 30 ); s.push(- 5 ); s.push( 18 ); s.push( 14 ); s.push(- 3 ); System.out.println( "Stack elements before sorting: " ); printStack(s); sortStack(s); System.out.println( " \n\nStack elements after sorting:" ); printStack(s); } }

Python3

# Python program to sort a stack using recursion# Recursive method to insert element in sorted waydef sortedInsert(s, element):# Base case: Either stack is empty or newly inserted # item is greater than top (more than all existing) if len (s) = = 0 or element > s[ - 1 ]: s.append(element) return else :# Remove the top item and recur temp = s.pop() sortedInsert(s, element)# Put back the top item removed earlier s.append(temp)# Method to sort stackdef sortStack(s):# If stack is not empty if len (s) ! = 0 :# Remove the top item temp = s.pop()# Sort remaining stack sortStack(s)# Push the top item back in sorted stack sortedInsert(s, temp)# Printing contents of stackdef printStack(s): for i in s[:: - 1 ]: print (i, end = " " ) print ()# Driver Code if __name__ = = '__main__' : s = [] s.append( 30 ) s.append( - 5 ) s.append( 18 ) s.append( 14 ) s.append( - 3 )print ( "Stack elements before sorting: " ) printStack(s)sortStack(s)print ( "\nStack elements after sorting: " ) printStack(s)# This code is contributed by Muskan Kalra.

C#

// C# program to sort a Stack using recursion // Note that here predefined Stack class is used // for stack operation using System; using System.Collections; public class GFG { // Recursive Method to insert an item x in sorted way static void sortedInsert(Stack s, int x) { // Base case: Either stack is empty or // newly inserted item is greater than top // (more than all existing) if (s.Count == 0 || x > ( int )s.Peek()) { s.Push(x); return ; }// If top is greater, remove // the top item and recur int temp = ( int )s.Peek(); s.Pop(); sortedInsert(s, x); // Put back the top item removed earlier s.Push(temp); }// Method to sort stack static void sortStack(Stack s) { // If stack is not empty if (s.Count > 0) { // Remove the top item int x = ( int )s.Peek(); s.Pop(); // Sort remaining stack sortStack(s); // Push the top item back in sorted stack sortedInsert(s, x); } }// Utility Method to print contents of stack static void printStack(Stack s) { foreach ( int c in s) { Console.Write(c + " " ); } }// Driver code public static void Main(String[] args) { Stack s = new Stack(); s.Push(30); s.Push(-5); s.Push(18); s.Push(14); s.Push(-3); Console.WriteLine( "Stack elements before sorting: " ); printStack(s); sortStack(s); Console.WriteLine( " \n\nStack elements after sorting:" ); printStack(s); } }// This code is Contibuted by Arnab Kundu

输出如下： 

Stack elements before sorting: -3 14 18 -5 30 Stack elements after sorting: 30 18 14 -3 -5

复杂度分析： 

• 时间复杂度：O(n^2)。
  在最坏的情况下sortstack(), sortedinsert()被递归调用" N"次, 以将元素放置在正确的位置
• 辅助空间：O(n^2)
  使用栈数据结构存储值

【如何使用递归对栈进行排序（算法实现）】如果发现任何不正确的地方, 或者想分享有关上述主题的更多信息, 请发表评论。

推荐阅读

• 

  自汗是什么意思 自汗解释
• 

  怎样熬排骨汤又白又浓
• 

  驾驶证年审手续流程是什么
• 

  高手在民间！！！
• 

  华为P40是几W快充（华为P40的快充是多少）
• 

  早起打卡第62天，早饭打卡第8天
• 

  生菜对环境条件的要求 生菜适合的温度和环境
• 

  经常吃猪肝对身体好吗 经常吃猪肝好不好
• 

  cf手游像我这个比较穷的V5买啥好？
• 

  弹弹堂安卓苹果互通吗,弹弹幽灵大冒险:苹果和安卓不完全互通
• 

  除了《恶作剧之吻》,你还记得哪些小时候看的青春偶像剧？
• 

  苦练郭林气功复发 郭林新气功
• 

  爱普生l360打印机废墨收集垫6
• 

  想问一下在京东买手机靠谱吗？
• 

  美股基金有哪些
• 

  redis槽满了会怎么样 redis的插槽不均匀
• 

  银河破裂者最高难度战役模式怎么玩 战役模式通关方法推荐
• 

  vue+echarts实带渐变效果的折线图
• 

  什么是不成对电子数
• 

  为什么热水器只能75度，怎么修复与排查方法？

• JavaScript布尔构造函数属性
• 如何使用MoviePy合成视频（设置单个剪辑的开始时间）
• JavaScript如何使用Date parse()方法（用法示例）
• Python程序可计算列表中的正数和负数
• jQuery如何使用多个ID选择器（代码示例）
• 检查给定字符串的字符是否可以重新排列以形成回文
• 算法设计（如何高效地找到数字的奇偶性（））
• 了解基本的JavaScript代码，简要指南
• 进程表和进程控制块（PCB）详细指南