【第三轮】6.30-7.6 CareerCup 3.1

//【解题思路】
//对半分，一半作为固定大小的栈，另一半作为大小可变的两个栈，其两端分别是两个栈的栈底
//当然，不一定要中点，可以根据需求分成两部分。
//【时间复杂度】
//
//【空间复杂度】
//
//【gist link】
https://gist.github.com/Tsien/66cb3eb43ad7f7e9c396

【解题思路】
stack 1 grows right from left-end, stack 2 grows left from right-end, stack 3 grows right from center. move stack 3 when necessary.
【时间复杂度】
O(N) for push operation
【空间复杂度】
O(1)
【gist link】
https://gist.github.com/b9921dbc553ed0fc31d3
【test case】
intput: see code.
output:
|1 1|0 0 0 0 0 0 0 0 |3 3|0 0 0 0 0 0 |2 2 |
|1 1|0 0 0 0 0 0 0 0 |3 3 4 4 4|0 0 0 |2 2 |
|1 1|0 0 0 0 0 0 0 0 |3 3 4 4 4||5 5 5 2 2 |
|1 1|0 0 0 0 |3 3 4 4 4|0 0 0 |6 5 5 5 2 2 |
|1 1 7 7 7 7||3 3 4 4 4|0 0 0 |6 5 5 5 2 2 |
|1 1 7 7 7 7 8|0 |3 3 4 4 4|0 |6 5 5 5 2 2 |
|1 1 7 7 7 7 8|0 |3 3 4 4 4 9||6 5 5 5 2 2 |
|1 1 7 7 7 7 8||3 3 4 4 4 9 10||6 5 5 5 2 2 |
No space available!
Pop out: 8
|1 1 7 7 7 7|0 |3 3 4 4 4 9 10||6 5 5 5 2 2 |
Pop out: 6
|1 1 7 7 7 7|0 |3 3 4 4 4 9 10|0 |5 5 5 2 2 |
Pop out: 10
|1 1 7 7 7 7|0 |3 3 4 4 4 9|0 0 |5 5 5 2 2 |
|1 1 7|0 0 0 0 |3 3 4|0 0 0 0 0 0 0 0 |2 2 |
|1 1 7|0 0 0 0 |3 3 4|0 0 0 0 0 0 0 0 0 0 |
Empty stack!
Press any key to continue . . .

这个题目的具体要求是什么呢？我感觉很多人都没有实现只有当三个栈全满时才增加栈的大小或者提示栈溢出。比如push到第一个栈时，第一个栈满了，应该看第二个栈是不是还有空位，如果第二个栈也满了再看第三个栈。如果push到第三个栈，也应该循环检查。

【解题思路】
1st stack grows from left to right
2nd stack grows from right to left
3rd stack grows from middle to both two sides
expand the arrary when collision happens among stacks

【时间复杂度】
O(1) amortized

【空间复杂度】
O(n)

【gist link】
https://gist.github.com/happyWinner/d5327096d4c7432ce330

【解题思路】
trick of index with a dynamic array
index1: 3n
index2: 3n+1
index3: 3n+2

【时间复杂度】
O(1) amortized

【空间复杂度】
O(n)

【gist link】
https://gist.github.com/Noahsark/83576ab8bf400edad01c

这题不难但是小bug太多
https://gist.github.com/daisyang/5521dd686dcb792ff86d