算法设计：如何使用递归反转栈(Stack)？

本文概述

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

编写程序以使用递归来反转栈(Stack)。不允许使用while, for..etc等循环构造, 并且只能在Stack S上使用以下ADT函数：

isEmpty(S)

push(S)

pop(S)

解决方案的想法是将所有值保留在函数调用栈中, 直到栈变空。当纸堆变空时, 将所有保留的物品一一插入纸堆底部。

例如, 让输入栈为

1  <-- top
    2
    3
    4

First 4 is inserted at the bottom.
    4 <-- top

Then 3 is inserted at the bottom
    4 <-- top    
    3

Then 2 is inserted at the bottom
    4 <-- top    
    3 
    2
     
Then 1 is inserted at the bottom
    4 <-- top    
    3 
    2
    1

因此, 我们需要一个函数, 该函数使用上述给定的基本栈函数插入栈的底部。

void insertAtBottom()：首先弹出所有栈项, 然后使用递归将弹出的项存储在函数调用栈中。并且当栈变空时, 推送新项目和所有存储在调用栈中的项目。

void reverse()：此函数主要使用insertAtBottom()逐一弹出所有项目, 然后将弹出的项目插入底部。

C ++

// C++ code to reverse a
// stack using recursion
#include<bits/stdc++.h>
using namespace std;
 
// using std::stack for
// stack implementation
stack< char > st;
 
// intializing a string to store
// result of reversed stack
string ns;
 
// Below is a recursive function
// that inserts an element
// at the bottom of a stack.
char insert_at_bottom( char x)
{
 
     if (st.size() == 0)
     st.push(x);
 
     else
     {
         
         // All items are held in Function Call
         // Stack until we reach end of the stack
         // When the stack becomes empty, the
         // st.size() becomes 0, the above if
         // part is executed and the item is
         // inserted at the bottom
             
         char a = st.top();
         st.pop();
         insert_at_bottom(x);
 
         // push allthe items held in
         // Function Call Stack
         // once the item is inserted
         // at the bottom
         st.push(a);
     }
}
 
// Below is the function that
// reverses the given stack using
// insert_at_bottom()
char reverse()
{
     if (st.size()>0)
     {
         
         // Hold all items in Function
         // Call Stack until we
         // reach end of the stack
         char x = st.top();
         st.pop();
         reverse();
         
         // Insert all the items held
         // in Function Call Stack
         // one by one from the bottom
         // to top. Every item is
         // inserted at the bottom
         insert_at_bottom(x);
     }
}
 
// Driver Code
int main()
{
     
     // push elements into
     // the stack
     st.push( '1' );
     st.push( '2' );
     st.push( '3' );
     st.push( '4' );
     
     cout<< "Original Stack" <<endl;
     
     // print the elements
     // of original stack
     cout<< "1" << " " << "2" << " "
         << "3" << " " << "4"
         <<endl;
     
     // function to reverse
     // the stack
     reverse();
     cout<< "Reversed Stack"
         <<endl;
     
     // storing values of reversed
     // stack into a string for display
     while (!st.empty())
     {
         char p=st.top();
         st.pop();
         ns+=p;
     }
     
     //display of reversed stack
     cout<<ns[3]<< " " <<ns[2]<< " "
         <<ns[1]<< " " <<ns[0]<<endl;
     return 0;
}
 
// This code is contributed by Gautam Singh

C

// C program to reverse a
// stack using recursion
#include<stdio.h>
#include<stdlib.h>
#define bool int
 
// structure of a stack node
struct sNode
{
     char data;
     struct sNode *next;
};
 
// Function Prototypes
void push( struct sNode** top_ref, int new_data);
int pop( struct sNode** top_ref);
bool isEmpty( struct sNode* top);
void print( struct sNode* top);
 
// Below is a recursive function
// that inserts an element
// at the bottom of a stack.
void insertAtBottom( struct sNode** top_ref, int item)
{
     if (isEmpty(*top_ref))
         push(top_ref, item);
     else
     {
 
         // Hold all items in Function Call
         // Stack until we reach end of the
         // stack. When the stack becomes
         // empty, the isEmpty(*top_ref)becomes
         // true, the above if part is executed
         // and the item is inserted at the bottom
         int temp = pop(top_ref);
         insertAtBottom(top_ref, item);
 
         // Once the item is inserted
         // at the bottom, push all
         // the items held in Function
         // Call Stack
         push(top_ref, temp);
     }
}
 
// Below is the function that
// reverses the given stack using
// insertAtBottom()
void reverse( struct sNode** top_ref)
{
     if (!isEmpty(*top_ref))
     {
         // Hold all items in Function
         // Call Stack until we
         // reach end of the stack
         int temp = pop(top_ref);
         reverse(top_ref);
 
         // Insert all the items (held in
         // Function Call Stack)
         // one by one from the bottom
         // to top. Every item is
         // inserted at the bottom
         insertAtBottom(top_ref, temp);
     }
}
 
// Driver Code
int main()
{
     struct sNode *s = NULL;
     push(&s, 4);
     push(&s, 3);
     push(&s, 2);
     push(&s, 1);
 
     printf ( "\n Original Stack " );
     print(s);
     reverse(&s);
     printf ( "\n Reversed Stack " );
     print(s);
     return 0;
}
 
// Function to check if
// the stack is empty
bool isEmpty( struct sNode* top)
{
     return (top == NULL)? 1 : 0;
}
 
// Function to push an item to stack
void push( struct sNode** top_ref, int new_data)
{
     
     // allocate node
     struct sNode* new_node =
         ( struct sNode*) malloc ( sizeof ( struct sNode));
 
     if (new_node == NULL)
     {
         printf ( "Stack overflow \n" );
         exit (0);
     }
 
     // put in the data
     new_node->data = new_data;
 
     // link the old list
     // off the new node
     new_node->next = (*top_ref);
 
     // move the head to
     // point to the new node
     (*top_ref) = new_node;
}
 
// Function to pop an item from stack
int pop( struct sNode** top_ref)
{
     char res;
     struct sNode *top;
 
     // If stack is empty then error
     if (*top_ref == NULL)
     {
         printf ( "Stack overflow \n" );
         exit (0);
     }
     else
     {
         top = *top_ref;
         res = top->data;
         *top_ref = top->next;
         free (top);
         return res;
     }
}
 
// Function to print a
// linked list
void print( struct sNode* top)
{
     printf ( "\n" );
     while (top != NULL)
     {
         printf ( " %d " , top->data);
         top = top->next;
     }
}

Java

// Java code to reverse a
// stack using recursion
import java.util.Stack;
 
class Test {
     
     // using Stack class for
     // stack implementation
     static Stack<Character> st = new Stack<>();
     
     // Below is a recursive function
     // that inserts an element
     // at the bottom of a stack.
     static void insert_at_bottom( char x)
     {
 
         if (st.isEmpty())
             st.push(x);
 
         else
         {
             
             // All items are held in Function
             // Call Stack until we reach end
             // of the stack. When the stack becomes
             // empty, the st.size() becomes 0, the
             // above if part is executed and
             // the item is inserted at the bottom
             char a = st.peek();
             st.pop();
             insert_at_bottom(x);
 
             // push allthe items held
             // in Function Call Stack
             // once the item is inserted
             // at the bottom
             st.push(a);
         }
     }
     
     // Below is the function that
     // reverses the given stack using
     // insert_at_bottom()
     static void reverse()
     {
         if (st.size() > 0 )
         {
             
             // Hold all items in Function
             // Call Stack until we
             // reach end of the stack
             char x = st.peek();
             st.pop();
             reverse();
             
             // Insert all the items held
             // in Function Call Stack
             // one by one from the bottom
             // to top. Every item is
             // inserted at the bottom
             insert_at_bottom(x);
         }
     }
     
     // Driver Code
     public static void main(String[] args)
     {
         
         // push elements into
         // the stack
         st.push( '1' );
         st.push( '2' );
         st.push( '3' );
         st.push( '4' );
         
         System.out.println( "Original Stack" );
         
         System.out.println(st);
         
         // function to reverse
         // the stack
         reverse();
         
         System.out.println( "Reversed Stack" );
         
         System.out.println(st);
     }
}

Python3

# Python program to reverse a
# stack using recursion
 
# Below is a recursive function
# that inserts an element
# at the bottom of a stack.
def insertAtBottom(stack, item):
     if isEmpty(stack):
         push(stack, item)
     else :
         temp = pop(stack)
         insertAtBottom(stack, item)
         push(stack, temp)
 
# Below is the function that
# reverses the given stack
# using insertAtBottom()
def reverse(stack):
     if not isEmpty(stack):
         temp = pop(stack)
         reverse(stack)
         insertAtBottom(stack, temp)
 
# Below is a complete running
# program for testing above
# functions.
 
# Function to create a stack.
# It initializes size of stack
# as 0
def createStack():
     stack = []
     return stack
 
# Function to check if
# the stack is empty
def isEmpty( stack ):
     return len (stack) = = 0
 
# Function to push an
# item to stack
def push( stack, item ):
     stack.append( item )
 
# Function to pop an
# item from stack
def pop( stack ):
 
     # If stack is empty
     # then error
     if (isEmpty( stack )):
         print ( "Stack Underflow " )
         exit( 1 )
 
     return stack.pop()
 
# Function to print the stack
def prints(stack):
     for i in range ( len (stack) - 1 , - 1 , - 1 ):
         print (stack[i], end = ' ' )
     print ()
 
# Driver Code
 
stack = createStack()
push( stack, str ( 4 ) )
push( stack, str ( 3 ) )
push( stack, str ( 2 ) )
push( stack, str ( 1 ) )
print ( "Original Stack " )
prints(stack)
 
reverse(stack)
 
print ( "Reversed Stack " )
prints(stack)
 
# This code is contributed by Sunny Karira

C#

// C# code to reverse a
// stack using recursion
using System;
using System.Collections;
 
public class GFG
{
 
     // using Stack class for
     // stack implementation
     static Stack st = new Stack();
     
     // Below is a recursive function
     // that inserts an element
     // at the bottom of a stack.
     static void insert_at_bottom( char x)
     {
 
         if (st.Count==0)
             st.Push(x);
 
         else
         {
             
             // All items are held in Function
             // Call Stack until we reach end
             // of the stack. When the stack becomes
             // empty, the st.size() becomes 0, the
             // above if part is executed and
             // the item is inserted at the bottom
             char a = ( char )st.Peek();
             st.Pop();
             insert_at_bottom(x);
 
             // push allthe items held
             // in Function Call Stack
             // once the item is inserted
             // at the bottom
             st.Push(a);
         }
     }
     
     // Below is the function that
     // reverses the given stack using
     // insert_at_bottom()
     static void reverse()
     {
         if (st.Count > 0)
         {
             
             // Hold all items in Function
             // Call Stack until we
             // reach end of the stack
             char x = ( char )st.Peek();
             st.Pop();
             reverse();
             
             // Insert all the items held
             // in Function Call Stack
             // one by one from the bottom
             // to top. Every item is
             // inserted at the bottom
             insert_at_bottom(x);
         }
     }
     
     // Driver Code
     public static void Main(String []args)
     {
         
         // push elements into
         // the stack
         st.Push( '1' );
         st.Push( '2' );
         st.Push( '3' );
         st.Push( '4' );
         
         Console.WriteLine( "Original Stack" );
         
         foreach ( char i in st)
         {
             Console.WriteLine(i);
         }
         
         // function to reverse
         // the stack
         reverse();
         
         Console.WriteLine( "Reversed Stack" );
         foreach ( char i in st)
         {
             Console.WriteLine(i);
         }
     }
 
}
 
// This code is Contibuted by Arnab Kundu

输出如下： 

Original Stack 
 1  2  3  4 
 Reversed Stack 
 4  3  2  1

时间复杂度：这种方法需要最差的时间复杂度O(n^2),

如果你发现上述代码/算法中的任何错误, 或者找到其他解决相同问题的方法, 请写评论。