【第三轮】6.30-7.6 CareerCup 3.6

3.6 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.


回复解法可以按照以下格式来

【解题思路】
【时间复杂度】
【空间复杂度】
【gist link】
---------------Optional，如果觉得test case比较好，欢迎写出来分享----------------------
【test case】

Notice：
1、记得在程序注释中表明自己算法的时间、空间复杂度
2、代码难懂之处加注释
3、每道题目有对应的帖子，除了贴解法，欢迎讨论，集思广益
4、任何未尽之处，欢迎回报名帖提问，我会进一步作出修改。

【解题思路】
If system stack can be considered as valid additional stack. Then we can have a recursive algorithm which leads to simple coding.

Pseudo code for Sorting:
Sort( stack with n elements)
       pop the top element out
       then recursively sort the stack with n-1 elements
       then insert the original top element to the right place

Pseudo Code for insert
Insert(stack with n elements, element)
       if stack is empty or the top element is less than or equal to element, then we just push this element into the stack
       otherwise(similar to the procedure in sort):
                      we fetch the top element of the stack
                      we recursively insert the element into the right place in the stack with n-1 element
                      then we put the original top element back

【时间复杂度】
O(n^2)
【空间复杂度】
O(n)
【gist link】
https://gist.github.com/ryancooper/fd37ad761c15da4c95d4

【解题思路】
方案一：如果不允许用Stack.size()函数，那么可以使用insertion sort，开一个额外的stack2，对于原stack中的最顶端的element，先pop进一个temp变量，如果比stack2.peek()大的话就直接push进stack2，否则一直将stack2中的元素pop进原stack，直到可以将该element push进stack2。该操作重复至原stack为空。空间为O(n)，时间为O(n^2)
方案二：如果允许使用Stack.size()函数，可以使用Merge sort。每次将一个stack的一半pop进另一个新开的stack，然后分别对其排序，需要注意的是，merge操作后顺序会变成descending的，因此还要reverse一下。空间为O(n)，时间为O(nlgn)
【时间复杂度】O(n^2) / O(nlgn)
【空间复杂度】O(n)     / O(n)
【gist link】https://gist.github.com/chouclee/7ecae00e8d7b540398a7

补充内容 (2014-6-30 16:09):
第一次是对的，反而编辑错了。。。merge-sort的空间应该是O(nlgn),
并且就算不可以stack.size()函数，也可以自己遍历一遍求出个数，空间和时间的复杂度不变。

【解题思路】
push and pop of two stacks.
【时间复杂度】
O(n^2)
【空间复杂度】
O(n)
【gist link】
https://gist.github.com/qianhuang/af02f882b1f6e4c7132c

chouclee 发表于 2014-6-30 00:21
【解题思路】
方案一：如果不允许用Stack.size()函数，那么可以使用insertion sort，开一个额外的stack2， ...

Your merge sort actually violates the question constraint, since we can use at most one additional stack. In your merge function, you use a third stack

ryancooper 发表于 2014-7-2 12:21
Your merge sort actually violates the question constraint, since we can use at most one additional ...

呀，没仔细看这里题目，谢谢指出。
我看的是第5版的书。。。那里是可以用多个stacks。。。

【解题思路】
similar as book solution but perform sort in place, use an additional stack to hold sorted elements (but in descending order so that the sorting can be STABLE!)
【时间复杂度】
O(N^2)
【空间复杂度】
O(N)
【gist link】
https://gist.github.com/e69d2cf5c66aee0fa17a
【test case】
Pay attention to cases where identical elements exist!

【解题思路
keep popping the top element, and inserting it in to the correct position into addition stack, then popping sorted elements back from the additional stack to the original one

【时间复杂度】
O(N^2)

【空间复杂度】
O(N)

【gist link】
https://gist.github.com/chrislukkk/8094d2bafe238cc966c1

ivycheung1208 发表于 2014-7-3 07:57
【解题思路】
similar as book solution but perform sort in place, use an additional stack to hold so ...

我这边的第五版说的是“may use additional stacks"

P.S 我搞懂了，我用的是12年出版的第五版，你们用的是13年出版的，囧囧。。。

chouclee 发表于 2014-7-2 21:55
我这边的第五版说的是“may use additional stacks"

P.S 我搞懂了，我用的是12年出版的第五版，你们 ...

所噶……不过解析里也有讨论可以用多个unlimited stacks的情况 就像你写的那样嗯……