【第三轮】6.30-7.6 CareerCup 3.6

【解题思路】
push and pop of two stacks, sort one element for one time
【时间复杂度】
O(n^2)
【空间复杂度】
O(n)
【gist link】
https://gist.github.com/JoyceeLee/d0deb8471e0a0897fe24

【解题思路】
1. at most one extra stack;    insert method to sort
2. if more than one extra stacks are allowed, use merge sort

【时间复杂度】1. O(n^2)  2. O(nlgn)
【空间复杂度】1.O(n)       2.O(n)
【gist link】https://gist.github.com/jyhjuzi/d8ce4f37872a1e255329

【解题思路】
// Variation of Insertion Sort by using an extra stack. Iterate through every item in the input stack
        // We need to find the right place to insert the item in the result stack
        // we need to pop every item that is larger than it and we can store them by pushing them in the input stack, and then we push the element in the result stack
【时间复杂度】
O(n^2)
【空间复杂度】
O(n)
【gist link】
https://gist.github.com/XiaoxiaoLi/34f1cdc635f1365a9f70

【解题思路】
Assign the top element to another variable, pop it and
compare with the elements in the other stack. If it is
larger, just push it into the stack. Otherwise, pop elements
from the stack and push into original stack until the
original element is larger.
【时间复杂度】O(N^2)
【空间复杂度】O(N)
【gist link】https://gist.github.com/JoshuaTang/269d132360db2047c50e

【解题思路】Use another stack to reverse the source stack, when pop and push find the match value
【时间复杂度】O(n^2)
【空间复杂度】O(n)
【gist link】https://gist.github.com/bitcpf/ae426595e81cfcc832a8

【解题思路】用一个临时变量来记录stack里的最大值，将该值赋进信的stack，以此类推
【时间复杂度】O(n^2)
【空间复杂度】O(n)
【gist】
https://github.com/donnice/donnice/blob/master/Q3_6
【Test】
代码里自带

【解题思路】
use temp stack to store the sorted elements, pop element from the original stack and insert to the temp stack
【时间复杂度】
O(N^2)
【空间复杂度】
O(N)
【gist link】
https://gist.github.com/iwilbert/02b8f9a6206c7739601c

【解题思路】use 2 stack for push and pop, sort one for each time
【时间复杂度】o(n^2)
【空间复杂度】o(n)
【gist link】https://gist.github.com/hilda8519/faf7ac0aa630fff10216

【解题思路】
pop element in the original stack to temp, compare temp with sorting stack, push larger element in sorting stack back to the original stack.
【时间复杂度】
O(N^2)
【空间复杂度】
O(N)
【gist link】https://gist.github.com/yokiy/9cb9c81a0b80be6e1b5e