This program sorts the elements in one stack using another temporary stack. The algorithm ensures that the temporary stack always holds the elements in sorted order, thus effectively sorting the stack by the end of the operations.

Program Structure

The sorting is done by manipulating two stacks:

• The input stack contains the original unsorted elements.
• The temporary stack is used to hold elements in sorted order.

During the sorting process, each element from the input stack is placed in the correct position in the temporary stack.

Python Code

def sort_stack(input_stack):
    temp_stack = []
    while input_stack:
        current = input_stack.pop()
        while temp_stack and temp_stack[-1] > current:
            input_stack.append(temp_stack.pop())
        temp_stack.append(current)
    return temp_stack

# Example Usage
original_stack = [34, 3, 31, 98, 92, 23]
sorted_stack = sort_stack(original_stack)
print("Sorted elements:", sorted_stack)

Explanation of the Code

• Function sort_stack: Takes the input stack as a parameter and initializes an empty temporary stack. It then iterates over each element in the input stack:
• Current element: Is temporarily held while checking if it can be pushed onto the temporary stack.
• Comparison and placement: If the top of the temporary stack has a value greater than the current element, that element is popped back into the input stack. This process continues until the correct position for the current element is found in the temporary stack, where it is then placed.
• Result: The temporary stack now holds all the elements sorted in ascending order and is returned as the sorted stack.

Usage

This sorting algorithm can be useful in scenarios where the use of additional data structures is limited to stacks. It’s particularly useful in constrained environments where memory usage needs to be minimized, or in specific programming challenges.