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

2021年3月29日16:14:40 发表评论 955 次浏览

## 本文概述

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;

// off the new node
new_node->next = (*top_ref);

// 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
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``````