Clona una pila sin usar espacio extra | conjunto 2

Dada una pila S , la tarea es copiar el contenido de la pila S dada a otra pila T manteniendo el mismo orden.

Ejemplos:

Entrada: Fuente:- |5| 
                         |4|
                         |3|
                         |2|
                         |1|
Salida: Destino:- |5| 
                                   |4|
                                   |3|
                                   |2|
                                   |1|

Entrada: Fuente:- |12| 
                         |13|
                         |14|
                         |15|
                         |16|
Salida: Destino:- |12| 
                                   |13|
                                   |14|
                                   |15|
                                   |16|

Revertir el enfoque basado en la pila : consulte la publicación anterior de este artículo para revertir el enfoque basado en la pila.

Complejidad de Tiempo: O(N 2 )
Espacio Auxiliar: O(1)

Enfoque basado en listas vinculadas: Consulte la publicación anterior de este artículo para conocer el enfoque basado en listas vinculadas.

Complejidad temporal: O(N)
Espacio auxiliar: O(1)

Enfoque basado en la recursión : el problema dado también se puede resolver mediante el uso de la recursión . Siga los pasos a continuación para resolver el problema:

  • Defina una función recursiva , digamos RecursiveCloneStack(stack<int> S, stack<int>Des) donde S es la pila de origen y Des es la pila de destino:
  • Inicialice una pila , diga Des para almacenar la pila de destino.
  • Ahora llame a la función RecursiveCloneStack(S, Des) para copiar los elementos de la pila de origen a la pila de destino.
  • Después de completar los pasos anteriores, imprima los elementos de la pila Des como resultado.

A continuación se muestra la implementación del enfoque anterior:

C++

// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Auxiliary function to copy elements
// of source stack to destination stack
void RecursiveCloneStack(stack<int>& S,
                         stack<int>& Des)
{
    // Base case for Recursion
    if (S.size() == 0)
        return;
 
    // Stores the top element of the
    // source stack
    int val = S.top();
 
    // Removes the top element of the
    // source stack
    S.pop();
 
    // Recursive call to the function
    // with remaining stack
    RecursiveCloneStack(S, Des);
 
    // Push the top element of the source
    // stack into the Destination stack
    Des.push(val);
}
 
// Function to copy the elements of the
// source stack to destination stack
void cloneStack(stack<int>& S)
{
    // Stores the destination stack
    stack<int> Des;
 
    // Recursive function call to copy
    // the source stack to the
    // destination stack
    RecursiveCloneStack(S, Des);
 
    cout << "Destination:- ";
    int f = 0;
 
    // Iterate until stack Des is
    // non-empty
    while (!Des.empty()) {
 
        if (f == 0) {
            cout << Des.top();
            f = 1;
        }
 
        else
            cout << "              "
                 << Des.top();
        Des.pop();
 
        cout << '\n';
    }
}
 
// Driver Code
int main()
{
    stack<int> S;
    S.push(1);
    S.push(2);
    S.push(3);
    S.push(4);
    S.push(5);
    cloneStack(S);
 
    return 0;
}

Java

// Java program for the above approach
import java.util.*;
public class Main
{
    static Stack<Integer> S = new Stack<Integer>();
    static Stack<Integer> Des = new Stack<Integer>(); // Stores the destination stack
      
    // Auxiliary function to copy elements
    // of source stack to destination stack
    static void RecursiveCloneStack()
    {
       
        // Base case for Recursion
        if (S.size() == 0)
            return;
        
        // Stores the top element of the
        // source stack
        int val = S.peek();
        
        // Removes the top element of the
        // source stack
        S.pop();
        
        // Recursive call to the function
        // with remaining stack
        RecursiveCloneStack();
        
        // Push the top element of the source
        // stack into the Destination stack
        Des.push(val);
    }
      
    // Function to copy the elements of the
    // source stack to destination stack
    static void cloneStack()
    {
        // Recursive function call to copy
        // the source stack to the
        // destination stack
        RecursiveCloneStack();
        
        System.out.print("Destination:- ");
        int f = 0;
        
        // Iterate until stack Des is
        // non-empty
        while (Des.size() > 0) {
        
            if (f == 0) {
                System.out.print(Des.peek());
                f = 1;
            }
        
            else
                System.out.print("              " + Des.peek());
            Des.pop();
        
            System.out.println();
        }
    }
     
  // Driver code
    public static void main(String[] args) {
        S.push(1);
        S.push(2);
        S.push(3);
        S.push(4);
        S.push(5);
        cloneStack();
    }
}
 
// This code is contributed by mukesh07.

Python3

# Python3 program for the above approach
 
S = []
Des = [] # Stores the destination stack
   
# Auxiliary function to copy elements
# of source stack to destination stack
def RecursiveCloneStack():
    
    # Base case for Recursion
    if (len(S) == 0):
        return
     
    # Stores the top element of the
    # source stack
    val = S[-1]
     
    # Removes the top element of the
    # source stack
    S.pop()
     
    # Recursive call to the function
    # with remaining stack
    RecursiveCloneStack()
     
    # Push the top element of the source
    # stack into the Destination stack
    Des.append(val)
   
# Function to copy the elements of the
# source stack to destination stack
def cloneStack():
    # Recursive function call to copy
    # the source stack to the
    # destination stack
    RecursiveCloneStack()
     
    print("Destination:- ", end = "")
    f = 0
     
    # Iterate until stack Des is
    # non-empty
    while len(Des) > 0:
        if (f == 0):
            print(Des[-1], end = "")
            f = 1
     
        else:
            print("             ", Des[-1], end = "")
        Des.pop()
     
        print()
 
S.append(1)
S.append(2)
S.append(3)
S.append(4)
S.append(5)
cloneStack()
 
# This code is contributed by decode2207.

C#

// C# program for the above approach
using System;
using System.Collections;
class GFG {
     
    static Stack S = new Stack();
    static Stack Des = new Stack(); // Stores the destination stack
     
    // Auxiliary function to copy elements
    // of source stack to destination stack
    static void RecursiveCloneStack()
    {
        // Base case for Recursion
        if (S.Count == 0)
            return;
       
        // Stores the top element of the
        // source stack
        int val = (int)S.Peek();
       
        // Removes the top element of the
        // source stack
        S.Pop();
       
        // Recursive call to the function
        // with remaining stack
        RecursiveCloneStack();
       
        // Push the top element of the source
        // stack into the Destination stack
        Des.Push(val);
    }
     
    // Function to copy the elements of the
    // source stack to destination stack
    static void cloneStack()
    {
        // Recursive function call to copy
        // the source stack to the
        // destination stack
        RecursiveCloneStack();
       
        Console.Write("Destination:- ");
        int f = 0;
       
        // Iterate until stack Des is
        // non-empty
        while (Des.Count > 0) {
       
            if (f == 0) {
                Console.Write(Des.Peek());
                f = 1;
            }
       
            else
                Console.Write("              " + Des.Peek());
            Des.Pop();
       
            Console.WriteLine();
        }
    }
 
  static void Main() {
    S.Push(1);
    S.Push(2);
    S.Push(3);
    S.Push(4);
    S.Push(5);
    cloneStack();
  }
}
 
// This code is contributed by divyesh072019.

Javascript

<script>
    // Javascript program for the above approach
    S = [];
    Des = []; // Stores the destination stack
      
    // Auxiliary function to copy elements
    // of source stack to destination stack
    function RecursiveCloneStack()
    {
     
        // Base case for Recursion
        if (S.length == 0)
            return;
        
        // Stores the top element of the
        // source stack
        let val = S[S.length - 1];
        
        // Removes the top element of the
        // source stack
        S.pop();
        
        // Recursive call to the function
        // with remaining stack
        RecursiveCloneStack();
        
        // Push the top element of the source
        // stack into the Destination stack
        Des.push(val);
    }
      
    // Function to copy the elements of the
    // source stack to destination stack
    function cloneStack()
    {
        // Recursive function call to copy
        // the source stack to the
        // destination stack
        RecursiveCloneStack();
        
        document.write("Destination:- ");
        let f = 0;
        
        // Iterate until stack Des is
        // non-empty
        while (Des.length > 0) {
        
            if (f == 0) {
                document.write(Des[Des.length - 1]);
                f = 1;
            }
        
            else{
                document.write("                      " + Des[Des.length - 1]);
            }
            Des.pop();
        
            document.write("</br>");
        }
    }
     
    S.push(1);
    S.push(2);
    S.push(3);
    S.push(4);
    S.push(5);
    cloneStack();
     
    // This code is contributed by suresh07.
</script>
Producción: 

Destination:- 5
              4
              3
              2
              1

 

Complejidad temporal: O(N) 
Espacio auxiliar: O(1)

Publicación traducida automáticamente

Artículo escrito por ajmrishav y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *