Dada una pila, ordénela usando recursividad. No se permite el uso de construcciones de bucle como while, for, etc. Solo podemos usar las siguientes funciones ADT en Stack S:
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.
Ejemplo:
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 check 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 check 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 Contributed by Arnab Kundu
Javascript
<script>
// JavaScript program to sort a Stack using recursion
// Note that here predefined Stack class is used
// for stack operation
// Recursive Method to insert an item x in sorted way
function sortedInsert(s,x)
{
// Base case: Either stack is empty or newly
// inserted item is greater than top (more than all
// existing)
if (s.length==0 || x > s[s.length-1])
{
s.push(x);
return;
}
// If top is greater, remove the top item and recur
let temp = s.pop();
sortedInsert(s, x);
// Put back the top item removed earlier
s.push(temp);
}
// Method to sort stack
function sortStack(s)
{
// If stack is not empty
if (s.length!=0)
{
// Remove the top item
let 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
function printStack(s)
{
for(let i=s.length-1;i>=0;i--)
{
document.write(s[i]+" ");
}
document.write("<br>")
}
// Driver code
let s=[];
s.push(30);
s.push(-5);
s.push(18);
s.push(14);
s.push(-3);
document.write(
"Stack elements before sorting: <br>");
printStack(s);
sortStack(s);
document.write(
" <br><br>Stack elements after sorting:<br>");
printStack(s);
// 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