Sort a stack

Last updated: 29th Aug, 2020

                 

Problem Statment

A stack is given. Sort the stack such that the top of the stack has the greatest element.

Input Format
10 2 45 3 7

Output Format
45 10 7 3 2
Approach :

1.Create two stack ( s1 , s2 ) and a temporary variable (temp)
2.The original stack (s1) should be greater than 0
3.Assign temp to the top element of the original stack , then push temp value into the another stack s2.
4.Now, again assign temp to the next top element of the original stack
5.Check if the temp value is greater than the s2
6.then push the temp value to original stack s1
7.Else push the temp value to s2
8.Return s2

Python Code

def sorted(s):
    s2 = createStack() 
    while(isEmpty(s) == False): 
        # pop out the first element 
        temp = top(s) 
        pop(s)

     # while temporary stack is not 
     # empty and top of stack is 
     # greater than temp 
     while(isEmpty(s2) == False and
        int(top(s2)) < int(temp)): 
                                      
        # pop from temporary stack and 
        # push it to the input stack 
        push(s,top(s2)) 
        pop(s2) 
                          
    # push temp in tempory of stack 
    push(s2,temp) 
                              
    return s2 
                        
def createStack(): 
    s = [] 
    return s 
                          
# Function to check if  
# the stack is empty 
def isEmpty( s ): 
    return len(s) == 0
                          
# Function to push an  
# item to stack
def push( s, item ): 
    s.append( item ) 
                          
# Function to get top  
# item of stack 
def top( s ): 
    a = len(s) 
    return s[a-1] 
                          
# Function to pop an  
# item from stack 
def pop( s ): 
                          
    # If stack is empty 
    # then error 
    if(isEmpty( s )): 
        print("Stack Underflow ") 
        exit(1) 
                          
    return s.pop() 
                          
# Function to print the stack 
def display(s): 
    for i in range(len(s)-1, -1, -1): 
        print(s[i], end = ' ') 
    print()
                        
                        
# Driver's Code 
s = createStack() 
push( s, str(4) ) 
push( s, str(7) ) 
push( s, str(10) ) 
push( s, str(9) ) 
push( s, str(1) ) 
push( s, str(11) ) 
  
print("Sorted elements are: ") 
sort_st = sorted ( s ) 
print(sort_st)