Ordenar una pila usando una pila temporal

Dada una pila de enteros, ordénela en orden ascendente usando otra pila temporal.

Ejemplos: 

Input : [34, 3, 31, 98, 92, 23]
Output : [3, 23, 31, 34, 92, 98]

Input : [3, 5, 1, 4, 2, 8]
Output : [1, 2, 3, 4, 5, 8] 

Algoritmo:

  1. Cree una pila temporal, digamos tmpStack .
  2. Si bien la pila de entrada NO está vacía, haga esto: 
    • Extraiga un elemento de la pila de entrada, llámelo temp
    • mientras que la pila temporal NO está vacía y la parte superior de la pila temporal es mayor que la temperatura, 
      extraiga de la pila temporal y empújela a la pila de entrada
    • empujar la temperatura en la pila temporal
  3. Los números ordenados están en tmpStack

Aquí hay una ejecución en seco del pseudocódigo anterior.  

input: [34, 3, 31, 98, 92, 23]

Element taken out: 23
input: [34, 3, 31, 98, 92]
tmpStack: [23]

Element taken out: 92
input: [34, 3, 31, 98]
tmpStack: [23, 92]

Element taken out: 98
input: [34, 3, 31]
tmpStack: [23, 92, 98]

Element taken out: 31
input: [34, 3, 98, 92]
tmpStack: [23, 31]

Element taken out: 92
input: [34, 3, 98]
tmpStack: [23, 31, 92]

Element taken out: 98
input: [34, 3]
tmpStack: [23, 31, 92, 98]

Element taken out: 3
input: [34, 98, 92, 31, 23]
tmpStack: [3]

Element taken out: 23
input: [34, 98, 92, 31]
tmpStack: [3, 23]

Element taken out: 31
input: [34, 98, 92]
tmpStack: [3, 23, 31]

Element taken out: 92
input: [34, 98]
tmpStack: [3, 23, 31, 92]

Element taken out: 98
input: [34]
tmpStack: [3, 23, 31, 92, 98]

Element taken out: 34
input: [98, 92]
tmpStack: [3, 23, 31, 34]

Element taken out: 92
input: [98]
tmpStack: [3, 23, 31, 34, 92]

Element taken out: 98
input: []
tmpStack: [3, 23, 31, 34, 92, 98]

final sorted list: [3, 23, 31, 34, 92, 98]

Implementación:

C++

// C++ program to sort a stack using an
// auxiliary stack.
#include <bits/stdc++.h>
using namespace std;
 
// This function return the sorted stack
stack<int> sortStack(stack<int> &input)
{
    stack<int> tmpStack;
 
    while (!input.empty())
    {
        // pop out the first element
        int tmp = input.top();
        input.pop();
 
        // while temporary stack is not empty and top
        // of stack is greater than temp
        while (!tmpStack.empty() && tmpStack.top() > tmp)
        {
            // pop from temporary stack and push
            // it to the input stack
            input.push(tmpStack.top());
            tmpStack.pop();
        }
 
        // push temp in temporary of stack
        tmpStack.push(tmp);
    }
 
    return tmpStack;
}
 
// main function
int main()
{
    stack<int> input;
    input.push(34);
    input.push(3);
    input.push(31);
    input.push(98);
    input.push(92);
    input.push(23);
 
    // This is the temporary stack
    stack<int> tmpStack = sortStack(input);
    cout << "Sorted numbers are:\n";
 
    while (!tmpStack.empty())
    {
        cout << tmpStack.top()<< " ";
        tmpStack.pop();
    }
}

Java

// Java program to sort a stack using
// a auxiliary stack.
import java.util.*;
 
class SortStack
{
    // This function return the sorted stack
    public static Stack<Integer> sortstack(Stack<Integer>
                                             input)
    {
        Stack<Integer> tmpStack = new Stack<Integer>();
        while(!input.isEmpty())
        {
            // pop out the first element
            int tmp = input.pop();
         
            // while temporary stack is not empty and
            // top of stack is greater than temp
            while(!tmpStack.isEmpty() && tmpStack.peek()
                                                 > tmp)
            {
                // pop from temporary stack and
                // push it to the input stack
            input.push(tmpStack.pop());
            }
             
            // push temp in temporary of stack
            tmpStack.push(tmp);
        }
        return tmpStack;
    }
     
    // Driver Code
    public static void main(String args[])
    {
        Stack<Integer> input = new Stack<Integer>();
        input.add(34);
        input.add(3);
        input.add(31);
        input.add(98);
        input.add(92);
        input.add(23);
     
        // This is the temporary stack
        Stack<Integer> tmpStack=sortstack(input);
        System.out.println("Sorted numbers are:");
     
        while (!tmpStack.empty())
        {
            System.out.print(tmpStack.pop()+" ");
        }
    }
}
// This code is contributed by Danish Kaleem

Python3

# Python program to sort a
# stack using auxiliary stack.
 
# This function return the sorted stack
def sortStack ( stack ):
    tmpStack = createStack()
    while(isEmpty(stack) == False):
         
        # pop out the first element
        tmp = top(stack)
        pop(stack)
 
        # while temporary stack is not
        # empty and top of stack is
        # greater than temp
        while(isEmpty(tmpStack) == False and
             int(top(tmpStack)) > int(tmp)):
             
            # pop from temporary stack and
            # push it to the input stack
            push(stack,top(tmpStack))
            pop(tmpStack)
 
        # push temp in temporary of stack
        push(tmpStack,tmp)
     
    return tmpStack
 
# Below is a complete running
# program for testing above
# function.
 
# 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 get top
# item of stack
def top( stack ):
    p = len(stack)
    return stack[p-1]
 
# 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(34) )
push( stack, str(3) )
push( stack, str(31) )
push( stack, str(98) )
push( stack, str(92) )
push( stack, str(23) )
 
print("Sorted numbers are: ")
sortedst = sortStack ( stack )
prints(sortedst)
 
# This code is contributed by
# Prasad Kshirsagar

C#

// C# program to sort a stack using
// a auxiliary stack.
using System;
using System.Collections.Generic;
 
class GFG
{
// This function return the sorted stack
public static Stack<int> sortstack(Stack<int> input)
{
    Stack<int> tmpStack = new Stack<int>();
    while (input.Count > 0)
    {
        // pop out the first element
        int tmp = input.Pop();
 
        // while temporary stack is not empty and
        // top of stack is greater than temp
        while (tmpStack.Count > 0 && tmpStack.Peek() > tmp)
        {
            // pop from temporary stack and
            // push it to the input stack
            input.Push(tmpStack.Pop());
        }
 
        // push temp in temporary of stack
        tmpStack.Push(tmp);
    }
    return tmpStack;
}
 
// Driver Code
public static void Main(string[] args)
{
    Stack<int> input = new Stack<int>();
    input.Push(34);
    input.Push(3);
    input.Push(31);
    input.Push(98);
    input.Push(92);
    input.Push(23);
 
    // This is the temporary stack
    Stack<int> tmpStack = sortstack(input);
    Console.WriteLine("Sorted numbers are:");
 
    while (tmpStack.Count > 0)
    {
        Console.Write(tmpStack.Pop() + " ");
    }
}
}
 
// This code is contributed by Shrikant13

Javascript

<script>
    // Javascript program to sort a stack using
    // a auxiliary stack.
     
    // This function return the sorted stack
    function sortstack(input)
    {
        let tmpStack = [];
        while (input.length > 0)
        {
            // pop out the first element
            let tmp = input.pop();
 
            // while temporary stack is not empty and
            // top of stack is greater than temp
            while (tmpStack.length > 0 && tmpStack[tmpStack.length - 1] > tmp)
            {
                // pop from temporary stack and
                // push it to the input stack
                input.push(tmpStack[tmpStack.length - 1]);
                tmpStack.pop()
            }
 
            // push temp in temporary of stack
            tmpStack.push(tmp);
        }
        return tmpStack;
    }
     
    let input = [];
    input.push(34);
    input.push(3);
    input.push(31);
    input.push(98);
    input.push(92);
    input.push(23);
   
    // This is the temporary stack
    let tmpStack = sortstack(input);
    document.write("Sorted numbers are:" + "</br>");
   
    while (tmpStack.length > 0)
    {
        document.write(tmpStack[tmpStack.length - 1] + " ");
        tmpStack.pop();
    }
     
    // This code is contributed by rameshtravel07.
</script>
Producción

Sorted numbers are:
98 92 34 31 23 3 

Complejidad de tiempo: O(n 2 ) donde n es el número total de enteros en la pila dada.
Espacio Auxiliar: O(n)

microsoft

Este artículo es una contribución de Aditya Nihal Kumar Singh . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks. 

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

Deja una respuesta

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