本文概述

• 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)
  使用栈数据结构存储值

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

推荐阅读

• 

  孩子游泳需要注意哪些问题？
• 

  北海道12月下雪了吗
• 

  丰田86算跑车吗86属于两门4座硬顶跑车 丰田86算跑车吗
• 

  晚上经常睡眠不好该怎么办
• 

  适合发朋友圈的爱情说说语录
• 

  用CDR绘制彩蛋简笔画的方法
• 

  哪款销售管理软件,能对每一个订单的发货情况进行查询？
• 

  教育过程的基本矛盾是什么
• 

  高铁发车后可以退票吗，高铁发车后可以退票吗人不在车站
• 

  沙石镇时光智能日历如何获得
• 

  以写景开头叙事的亲情中考满分作文
• 

  结婚戒指的戴法有区别吗？ 婚戒戴法
• 

  粉底液分层了还可以用吗
• 

  西游记95回内容概括 西游记60回概括
• 

  rw渡劫亚瑟带队友击败xq,其亚瑟出装铭文曝光,居然是“暴击冷却”路线,值得推荐吗？
• 

  大众途观和翼虎到底哪个好 昂科威和翼虎哪个好
• 

  理想之城收视率怎么样
• 

  黄体酮|女性缺乏黄体酮，竟然有这么多危害！身体会给出哪些暗示？
• 

  休闲山庄怎么玩不了游戏，休闲山庄需要什么手续
• 

  海绵是如何进食的

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