codebytes: Sorting a given stack using one additional stack.

Related: Sort a stack using recursion - GeeksforGeeks
codebytes: Sorting a given stack using one additional stack.
Q. 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.


Algorithm:

1. We will have two stacks, first one is the given unsorted one and the second one will be sorted which will be returned by the method call.
2. Pop an item from first stack and push it to the second.
3. Pop an item from the unsorted (first) stack (storing it in a temp variable) and compare it with sorted array's head. If head is larger, pop it and push it to unsorted stack. Do this until the value at head is < or = to the temp element.
4. At the time when the loop stops, the value below is less than or equal to temp variable, we can now push it to the sorted stack.
5. Now push back all the items that were originally in stack 2 and were shifted to stack 1 to accommodate the temp item.
6. Do this until stack 1 becomes empty.
7. Stack 2 contains the sorted data and can now be returned.

    public static <T extends Comparable<T>> OrderedStack<T> sort(Stack<T> unsorted){
        OrderedStack<T> sorted = new OrderedStack<>(unsorted.size());
        if(unsorted.isEmpty())return sorted;
        
        sorted.push(unsorted.pop());
        while(!unsorted.isEmpty()){
            T temp = unsorted.pop(); 
            int i=0; 
            while(!sorted.isEmpty() && sorted.peek().compareTo(temp)>0){
                unsorted.push(sorted.pop());i++;
            }
            sorted.push(temp);
            while(i--!=0)sorted.push(unsorted.pop());
        }
        return sorted;
    } 

http://www.cnblogs.com/easonliu/p/4656772.html

 3     vector<int> twoStacksSort(vector<int> numbers) {
 4         // write code here
 5         stack<int> stk;
 6         int top = 0, tmp;
 7         while (top != numbers.size()) {
 8             tmp = numbers[top++];
 9             while (!stk.empty() && stk.top() > tmp) {
10                 numbers[--top] = stk.top();
11                 stk.pop();
12             }
13             stk.push(tmp);
14         }
15         top = 0;
16         while (!stk.empty()) {
17             numbers[top++] = stk.top();
18             stk.pop();
19         }
20         return numbers;
21     }

http://www.cnblogs.com/easonliu/p/4656772.html

请编写一个程序，按升序对栈进行排序（即最大元素位于栈顶），要求最多只能使用一个额外的栈存放临时数据，但不得将元素复制到别的数据结构中。

给定一个int[] numbers(C++中为vector<int>)，其中第一个元素为栈顶，请返回排序后的栈。请注意这是一个栈，意味着排序过程中你只能访问到第一个元素。

测试样例：

[1,2,3,4,5]

返回：[5,4,3,2,1]

Read full article from codebytes: Sorting a given stack using one additional stack.