Invertir una pila usando dos pilas vacías

Dada una pila S , la tarea es invertir la pila S usando dos pilas adicionales.

Ejemplo:

Entrada: S={1, 2, 3, 4, 5}
Salida: 5 4 3 2 1
Explicación:
La pila inicial S:
1→top
2
3
4
5
Después de invertirla, use dos pilas adicionales:
5→top
4
3
2
1

Entrada: S={1, 25, 17}
Salida: 17 25 1

Enfoque: siga los pasos a continuación para resolver el problema:

1. Cree dos pilas vacías adicionales , digamos A y B.
2. Defina una función transfer() que acepte dos pilas X e Y como parámetros y realice las siguientes operaciones:
   1. Haga un bucle mientras X no esté vacío y realice las siguientes operaciones:
      1. Empuje el elemento superior de la pila X en Y .
      2. Pop ese elemento de X .
3. Call transfer(S, A) tos transfiere todos los elementos de la pila S a A . ( Se invierte el orden de los elementos ).
4. Llame a transfer(A, B) para transferir todos los elementos de la pila A a B. ( El orden de los elementos es el mismo que inicialmente en S )
5. Call transfer(B, S) para transferir todos los elementos de B a S . ( El orden de los elementos se invierte )
6. Finalmente, muestre la pila S .

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

// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to transfer elements
// from the stack X to the stack Y
void transfer(stack<int>& X,
              stack<int>& Y)
{
    // Iterate while X is not empty
    while (!X.empty()) {
 
        // Push the top element
        // of X into Y
        Y.push(X.top());
 
        // Pop from X
        X.pop();
    }
}
 
// Function to display the
// contents of the stack S
void display(stack<int> S)
{
    // Iterate while S is
    // not empty
    while (!S.empty()) {
 
        // Print the top
        // element of the stack S
        cout << S.top() << " ";
 
        // Pop from S
        S.pop();
    }
    cout << endl;
}
 
// Function to reverse a stack using two stacks
void reverseStackUsingTwoStacks(stack<int>& S)
{
    // Two additional stacks
    stack<int> A, B;
 
    // Transfer all elements
    // from the stack S to A
    transfer(S, A);
 
    // Transfer all elements
    // from the stack A to B
    transfer(A, B);
 
    // Transfer all elements
    // from the stack B to S
    transfer(B, S);
 
    // Print the contents of S
    display(S);
}
// Driver Code
int main()
{
    // Input
    stack<int> S;
    S.push(5);
    S.push(4);
    S.push(3);
    S.push(2);
    S.push(1);
 
    // Function call
    reverseStackUsingTwoStacks(S);
 
    return 0;
}

// Java program for the above approach
import java.util.Stack;
public class GFG
{
 
    // Function to transfer elements
    // from the stack X to the stack Y
    static void transfer(Stack<Integer> X, Stack<Integer> Y)
    {
        // Iterate while X is not empty
        while (!X.empty())
        {
 
            // Push the top element
            // of X into Y
            Y.push(X.peek());
 
            // Pop from X
            X.pop();
        }
    }
 
    // Function to display the
    // contents of the stack S
    static void display(Stack<Integer> S)
    {
        // Iterate while S is
        // not empty
        while (!S.empty()) {
 
            // Print the top
            // element of the stack S
            System.out.print(S.peek() + " ");
 
            // Pop from S
            S.pop();
        }
        System.out.println();
    }
 
    // Function to reverse a stack using two stacks
    static void reverseStackUsingTwoStacks(Stack<Integer> S)
    {
        // Two additional stacks
        Stack<Integer> A = new Stack<>();
        Stack<Integer> B = new Stack<>();
 
        // Transfer all elements
        // from the stack S to A
        while (!S.empty())
            A.push(S.pop());
 
        // Transfer all elements
        // from the stack A to B
        while (!A.empty())
            B.push(A.pop());
 
        // Transfer all elements
        // from the stack B to S
        while (!B.empty())
            S.push(B.pop());
 
        // Print the contents of S
        display(S);
    }
 
    // Driver code
    public static void main(String[] args)
    {
       
      // Given Input
      // Input
        Stack<Integer> S = new Stack<>();
        S.push(5);
        S.push(4);
        S.push(3);
        S.push(2);
        S.push(1);
 
        // Function call
        reverseStackUsingTwoStacks(S);
    }
}
 
// This code is contributed by abhinavjain194

# Python3 program for the above approach
 
# Function to display the
# contents of the stack S
def display(S):
   
    # Iterate while S is
    # not empty
    while len(S) > 0:
 
        # Print the top
        # element of the stack S
        print(S[-1], end = " ")
 
        # Pop from S
        S.pop()
    print()
 
# Function to reverse a stack using two stacks
def reverseStackUsingTwoStacks(S):
   
    # Two additional stacks
    A = []
    B = []
        
    # Transfer all elements
    # from the stack S to A
    while len(S) > 0:
        A.append(S[-1])
        S.pop()
        
    # Transfer all elements
    # from the stack A to B
    while len(A) > 0:
        B.append(A[-1])
        A.pop()
        
    # Transfer all elements
    # from the stack B to S
    while len(B) > 0:
        S.append(B[-1])
        B.pop()
        
    # Print the contents of S
    display(S)
 
# Given Input
# Input
S = []
S.append(5)
S.append(4)
S.append(3)
S.append(2)
S.append(1)
 
# Function call
reverseStackUsingTwoStacks(S)
 
# This code is contributed by suresh07.

// C# program for the above approach
using System;
using System.Collections;
class GFG {
     
    // Function to transfer elements
    // from the stack X to the stack Y
    static void transfer(Stack X, Stack Y)
    {
        // Iterate while X is not empty
        while (X.Count > 0)
        {
  
            // Push the top element
            // of X into Y
            Y.Push(X.Peek());
  
            // Pop from X
            X.Pop();
        }
    }
  
    // Function to display the
    // contents of the stack S
    static void display(Stack S)
    {
        // Iterate while S is
        // not empty
        while (S.Count > 0) {
  
            // Print the top
            // element of the stack S
            Console.Write(S.Peek() + " ");
  
            // Pop from S
            S.Pop();
        }
        Console.WriteLine();
    }
  
    // Function to reverse a stack using two stacks
    static void reverseStackUsingTwoStacks(Stack S)
    {
        // Two additional stacks
        Stack A = new Stack();
        Stack B = new Stack();
  
        // Transfer all elements
        // from the stack S to A
        while (S.Count > 0)
            A.Push(S.Pop());
  
        // Transfer all elements
        // from the stack A to B
        while (A.Count > 0)
            B.Push(A.Pop());
  
        // Transfer all elements
        // from the stack B to S
        while (B.Count > 0)
            S.Push(B.Pop());
  
        // Print the contents of S
        display(S);
    }
 
  static void Main() {
    // Given Input
    // Input
    Stack S = new Stack();
    S.Push(5);
    S.Push(4);
    S.Push(3);
    S.Push(2);
    S.Push(1);
 
    // Function call
    reverseStackUsingTwoStacks(S);
  }
}
 
// This code is contributed by divyesh072019.

<script>
    // Javascript program for the above approach
   
    // Function to display the
    // contents of the stack S
    function display(S)
    {
        // Iterate while S is
        // not empty
        while (S.length > 0) {
   
            // Print the top
            // element of the stack S
            document.write(S[S.length - 1] + " ");
   
            // Pop from S
            S.pop();
        }
        document.write("</br>");
    }
   
    // Function to reverse a stack using two stacks
    function reverseStackUsingTwoStacks(S)
    {
        // Two additional stacks
        let A = [];
        let B = [];
           
        // Transfer all elements
        // from the stack S to A
        while (S.length > 0)
        {
            A.push(S[S.length - 1]);
            S.pop();
        }
           
        // Transfer all elements
        // from the stack A to B
        while (A.length > 0)
        {
            B.push(A[A.length - 1]);
            A.pop();
        }
           
        // Transfer all elements
        // from the stack B to S
        while (B.length > 0)
        {
            S.push(B[B.length - 1]);
            B.pop();
        }
           
        // Print the contents of S
        display(S);
    }
     
    // Given Input
    // Input
    let S = [];
    S.push(5);
    S.push(4);
    S.push(3);
    S.push(2);
    S.push(1);
  
    // Function call
    reverseStackUsingTwoStacks(S);
     
    // This code is contributed by mukesh07.
</script>

5 4 3 2 1

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