150 DSA

Sort Stack

📖Guides
👤
- Kapil Vaishnav
⭐
Beginner Level
🏷️
- 150 DSA
📅06 August 2023

Write a program to sort a stack such that the smallest items are on the top. You can use an additional temporary stack, but you may not copy the elements into any other data structure (such as an array). The stack supports the following operations: push, pop, peek, and is Empty.

The question asks us to implement a program to sort a stack in ascending order, where the smallest items are on the top. We are allowed to use an additional temporary stack, but we cannot copy the elements into any other data structure such as an array. The stack supports the following operations: push, pop, peek, and isEmpty.

🌟 To solve this problem, we can use the following approach:

Create two stacks: mainStack and tempStack.
While the mainStack is not empty:
- Pop the top element from the mainStack and store it in a variable called temp.
- While the tempStack is not empty and the top element of the tempStack is greater than temp, pop elements from the tempStack and push them back to the mainStack.
- Push temp onto the tempStack.
After the above steps, the tempStack will contain the sorted stack, with the smallest items on the top.
If needed, you can transfer the elements back to the mainStack while maintaining the sorted order.

💥 Code For Problem

cpp Code Snippet

#include <iostream>
#include <stack>

void sortStack(std::stack<int>& mainStack) {
    std::stack<int> tempStack;

    while (!mainStack.empty()) {
        int temp = mainStack.top();
        mainStack.pop();

        while (!tempStack.empty() && tempStack.top() > temp) {
            mainStack.push(tempStack.top());
            tempStack.pop();
        }

        tempStack.push(temp);
    }

    // Transfer elements back to the mainStack (optional)
    while (!tempStack.empty()) {
        mainStack.push(tempStack.top());
        tempStack.pop();
    }
}

int main() {
    std::stack<int> stack;

    // Push elements onto the stack
    stack.push(5);
    stack.push(2);
    stack.push(7);
    stack.push(1);

    // Sort the stack
    sortStack(stack);

    // Pop and print the sorted elements
    while (!stack.empty()) {
        std::cout << stack.top() << " ";
        stack.pop();
    }
    std::cout << std::endl;

    return 0;
}
                

😇 Explanation:

We create a stack called mainStack and push the elements onto it: 5, 2, 7, and 1.
We call the sortStack function, passing mainStack as a reference.
In the sortStack function, we create a temporary stack called tempStack.
We iterate through mainStack until it becomes empty:
- We pop the top element from mainStack and store it in the temp variable.
- We compare temp with the elements in tempStack and transfer elements from tempStack to mainStack if they are greater than temp.
- We push temp onto tempStack.
After the sorting is done, we can transfer the elements from tempStack back to mainStack if needed.
Finally, we pop and print the elements from mainStack, which are now sorted in ascending order: 1, 2, 5, 7.