如何使用递归对栈进行排序？算法实现

2021年4月1日15:32:55 发表评论 1,870 次浏览

本文概述

给定一个栈, 使用递归对其进行排序。不允许使用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 = 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 = 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 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(
             " \n\nStack 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 ( "\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)
    使用栈数据结构存储值

如果发现任何不正确的地方, 或者想分享有关上述主题的更多信息, 请发表评论。

木子山

发表评论

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: