算法设计（如何使用递归反转栈(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 < -- topThen 3 is inserted at the bottom 4 < -- top 3Then 2 is inserted at the bottom 4 < -- top 3 2Then 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 bottomchar 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 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 = https://www.lsbin.com/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# 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

输出如下：