给定一个堆栈，使用递归对其进行排序。使用任何循环构造，如while、for。。etc是不允许的。我们只能在堆栈S上使用以下ADT函数：
null
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 stack1418-530
让我们用上面的例子来说明堆栈的排序： 首先从堆栈中弹出所有元素，并将弹出的元素存储在变量“temp”中。弹出所有元素后，函数的堆栈框架将如下所示：
temp = -3 --> stack frame #1temp = 14 --> stack frame #2temp = 18 --> stack frame #3temp = -5 --> stack frame #4temp = 30 --> stack frame #5
现在堆栈为空，调用“insert_in_sorted_order（）”函数，并在堆栈底部插入30个（来自堆栈帧#5）。现在，堆栈如下所示：
30 <-- top of the stack
现在拾取下一个元素，即-5（来自堆栈帧#4）。由于-5<30，-5插入堆栈底部。现在stack变成：
30 <-- top of the stack-5
下一个18（从堆栈帧#3）被拾取。由于18<30，18插入到30以下。现在stack变成：
30 <-- top of the stack18 -5
接下来的14个（从堆栈帧#2）被拾取。由于14<30和14<18，它被插入18以下。现在stack变成：
30 <-- top of the stack1814 -5
现在-3（来自堆栈帧#1）被拾取，当-3<30、-3<18和-3<14时，它被插入到14下面。现在stack变成：
30 <-- top of the stack1814-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 check 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." ); return ; } p->data = 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 << "" ; } // 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:" ; printStack(top); sortStack(&top); cout << "" ; cout << "Stack elements after sorting:" ; 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 check 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." ); return ; } p->data = 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 ( "" ); } // 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:" ); printStack(top); sortStack(&top); printf ( "" ); printf ( "Stack elements after sorting:" ); printStack(top); return 0; } |
JAVA
// Java program to sort a Stack using recursion // Note that here predefined Stack class is used // for stack operation import 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( " Stack elements after sorting:" ); printStack(s); } } |
Python3
# Python program to sort a stack using recursion # Recursive method to insert element in sorted way def 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 stack def 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 stack def 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 ( "Stack 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( " Stack elements after sorting:" ); printStack(s); } } // This code is Contributed by Arnab Kundu |
Javascript
<script> // JavaScript program to sort a Stack using recursion // Note that here predefined Stack class is used // for stack operation // Recursive Method to insert an item x in sorted way function sortedInsert(s,x) { // Base case: Either stack is empty or newly // inserted item is greater than top (more than all // existing) if (s.length==0 || x > s[s.length-1]) { s.push(x); return ; } // If top is greater, remove the top item and recur let temp = s.pop(); sortedInsert(s, x); // Put back the top item removed earlier s.push(temp); } // Method to sort stack function sortStack(s) { // If stack is not empty if (s.length!=0) { // Remove the top item let 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 function printStack(s) { for (let i=s.length-1;i>=0;i--) { document.write(s[i]+ " " ); } document.write( "<br>" ) } // Driver code let s=[]; s.push(30); s.push(-5); s.push(18); s.push(14); s.push(-3); document.write( "Stack elements before sorting: <br>" ); printStack(s); sortStack(s); document.write( " <br><br>Stack elements after sorting:<br>" ); printStack(s); // This code is contributed by avanitrachhadiya2155 </script> |
输出：
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） 使用堆栈数据结构存储值
练习： 修改上面的代码以按降序反转堆栈。
本文由Narendra Kangralkar撰稿。如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写评论
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
