Stack Sorting (Ladder)

Description

Sort a stack in ascending order (with biggest terms 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 (e.g. array).

Example

Given stack =
| |
|3|
|1|
|2|
|4|
return:
| |
|4|
|3|
|2|
|1|

The data will be serialized to [4,2,1,3]. The last element is the element on the top of the stack.

Challenge
O(n^2) time is acceptable.

Link

Lintcode_ladder

Method

1. x
2. x

Example

1. 1

   class Solution {
   public:
    /**
     * @param stk an integer stack
     * @return void
     */
    void stackSorting(stack<int>& stk) {
        // Write your code here
        if (stk.empty()) {
            return;
        }
        stack<int> buf;
        int min = INT_MAX;
        while (!stk.empty()) {
            // has ascending order 
            if (buf.empty() || stk.top() <= buf.top()) {
                int tmp = stk.top();
                stk.pop();
                buf.push(tmp);
            } else {
            // has decreasing order
                int cur = stk.top();
                stk.pop();
                // fill back when cur >= buf.top()
                // until find the right order in the buf  
                while (!buf.empty() && cur >= buf.top()) {
                    int tmp = buf.top();
                    buf.pop();
                    stk.push(tmp);
                }
                stk.push(cur);
                // fill back rest 
                while (!buf.empty()) {
                    int tmp = buf.top();
                    buf.pop();
                    stk.push(tmp);
                }
            }
        }
        while (!buf.empty()) {
            int tmp = buf.top();
            buf.pop();
            stk.push(tmp);
        }
        return;
    }
   };
   

Similar problems

x

Tags

x