Cracking The Coding Interview/Q 3.6

From Software Engineers Wiki
Jump to: navigation, search

Write a program to sort a stack in ascending order (with biggest items on top). You may use at most one additional stack to hold items, 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 isEmpty.

Answer

Use a temporary stack to keep the elements in sorted order.

#include <stack>

template <typename T> void sort_stack(std::stack<T> &rstack)
{
        std::stack<T> tmp_stack;
        T value;

        if (rstack.empty())
                return;

        /* move all elements to tmp_stack in sorted way */
        while (!rstack.empty()) {
                int count;

                /* pop an element from the stack */
                value = rstack.top();
                rstack.pop();

                /* push to the tmp_stack in sorted way */
                for (count = 0; !tmp_stack.empty() && value < tmp_stack.top(); ++count) {
                        T tmp_value = tmp_stack.top();
                        tmp_stack.pop();
                        rstack.push(tmp_value);
                }
                tmp_stack.push(value);
                while (count-- > 0) {
                        T tmp_value = rstack.top();
                        rstack.pop();
                        tmp_stack.push(tmp_value);
                }
        }

        /* move all elements back to original stack */
        while (!tmp_stack.empty()) {
                T tmp_value = tmp_stack.top();
                tmp_stack.pop();
                rstack.push(tmp_value);
        }
}

Test program:

#include <iostream>

template <typename T> void print_stack_r(std::stack<T> &rstack)
{
        if (rstack.empty())
                return;
        int data = rstack.top();
        std::cout << data << " ";
        rstack.pop();
        print_stack_r(rstack);
        rstack.push(data);
}

template <typename T> void print_stack(std::stack<T> &rstack)
{
        print_stack_r(rstack);

        std::cout << std::endl;
}

int main(void)
{
        std::stack<int> my_stack { { 9, 5, 8, 4, 7, 3, 6, 1, 2 } };

        print_stack<int>(my_stack);
        sort_stack<int>(my_stack);
        print_stack<int>(my_stack);

        return 0;
}

Test result:

2 1 6 3 7 4 8 5 9 
1 2 3 4 5 6 7 8 9 
Personal tools
Namespaces

Variants
Actions
Navigation
Toolbox