"""
My solution:
Time Complexity:
The main loop iterates through each element in the original stack once.
In the worst case, for each element, you might have to pop elements from the temporary stack until
the correct position is found.
Therefore, the time complexity is O(N^2), where N is the number of elements in the stack.
Space Complexity:
The space complexity is O(N) since you are using two additional stacks
(original_stack and temp_stack), and their combined size depends on the number of elements in the original stack.
"""
class Node:
    def __init__(self, data):
        self.data = data
        self.next = None
class Stack:

    def __init__(self):
        self.top = None
        self.count = 0
    def size(self):
        return self.count

    def is_empty(self):
        return self.top is None
    def peek(self):
        if self.is_empty():
            return IndexError('Peek on empty stack')
        return self.top.data

    def pop(self):
        if self.is_empty():
            return IndexError('Pop on empty stack')
        popped_node = self.top
        self.top = self.top.next
        self.count -= 1
        return popped_node.data

    def push(self, data):
        new_node = Node(data)
        new_node.next = self.top
        self.top = new_node
        self.count += 1
"""
1. Input: [34, 3, 31, 98, 92, 23]
   Output: [3, 23, 31, 34, 92, 98]
2. Input: [4, 3, 2, 10, 12, 1, 5, 6]
   Output: [1, 2, 3, 4, 5, 6, 10, 12]
3. Input: [20, 10, -5, -1]
   Output: [-5, -1, 10, 20]
"""
class Solution:
    def sortStack(self, stack):
        o_stack = Stack()
        temp_stack = Stack()

        [o_stack.push(el) for el in stack]

        while o_stack.size():
            temp_val = o_stack.pop()
            while temp_stack.size() and temp_stack.peek() < temp_val:
                o_stack.push(temp_stack.pop())
            temp_stack.push(temp_val)

        return temp_stack