This C++ program demonstrates how to sort a stack using only another temporary stack. The program sorts the original stack in ascending order where the smallest elements end up on the top of the stack.

Program Code

#include <iostream>
#include <stack>

/**
 * Sorts a stack using another stack.
 * @param input Stack to be sorted.
 * @return A sorted stack where the smallest items are on top.
 */
std::stack<int> sortStack(std::stack<int>& input) {
    std::stack<int> tempStack;

    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 (!tempStack.empty() && tempStack.top() > tmp) {
            // pop from temporary stack and push
            // it to the input stack
            input.push(tempStack.top());
            tempStack.pop();
        }

        // push temp in tempory of stack
        tempStack.push(tmp);
    }

    return tempStack;
}

int main() {
    std::stack<int> input;
    input.push(34);
    input.push(3);
    input.push(31);
    input.push(98);
    input.push(92);
    input.push(23);

    // Function call to sort the stack
    std::stack<int> sortedStack = sortStack(input);

    std::cout << "Sorted numbers are:\n";

    while (!sortedStack.empty()) {
        std::cout << sortedStack.top() << " ";
        sortedStack.pop();
    }

    return 0;
}

Function Documentation

std::stack<int> sortStack(std::stack<int>& input)

This function sorts an input stack using another stack and returns the sorted stack.

• Parameters:
  • input: Reference to the stack that needs to be sorted.
• Returns: A sorted stack with the smallest items on top.
• Description:The function utilizes a temporary stack to hold elements in sorted order. Elements from the input stack are popped and compared with the elements of the temporary stack. If the current element from the input stack is smaller than the top of the temporary stack, elements from the temporary stack are moved back to the input stack until the correct position for the current element is found in the temporary stack.

Example Usage

        std::stack<int> input;
        input.push(34);
        input.push(3);
        input.push(31);
        input.push(98);
        input.push(92);
        input.push(23);

        std::stack<int> sortedStack = sortStack(input);

        while (!sortedStack.empty()) {
            std::cout << sortedStack.top() << " ";
            sortedStack.pop();
        }

This will output: 3 23 31 34 92 98