Escriba un programa para invertir una pila usando recursividad. No está permitido usar construcciones de bucle como while, for..etc, y solo puede usar las siguientes funciones ADT en Stack S:
isEmpty(S)
push(S)
pop(S)
La idea de la solución es mantener todos los valores en la pila de llamadas de función hasta que la pila se vacíe. Cuando la pila esté vacía, inserte todos los elementos retenidos uno por uno en la parte inferior de la pila.
Por ejemplo, deje que la pila de entrada sea
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;
// initializing 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.
void 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()
void 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 all the 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 Contributed by Arnab Kundu
Javascript
<script>
// JavaScript code to reverse a
// stack using recursion
// using Stack class for
// stack implementation
let st = [];
// Below is a recursive function
// that inserts an element
// at the bottom of a stack.
function insert_at_bottom(x)
{
if(st.length==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
let a = 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()
function reverse()
{
if(st.length > 0)
{
// Hold all items in Function
// Call Stack until we
// reach end of the stack
let x = 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
// push elements into
// the stack
st.push('1');
st.push('2');
st.push('3');
st.push('4');
document.write("Original Stack<br>");
document.write(st.join(" ")+"<br>");
// function to reverse
// the stack
reverse();
document.write("Reversed Stack<br>");
document.write(st.join(" "));
// This code is contributed by avanitrachhadiya2155
</script>
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA