【第四轮】4.13 - 4.19 Career Cup 3.5

3.5 Implement a MyQueue class which implements a queue using two stacks

【解题思路】
【时间复杂度】
【空间复杂度】
【gist link]
【test case】(optional，如果觉得比较好，欢迎贴出来分享）

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

[solution]
when pushing number x to the queue:
1)push x to the first stack
when popping element from the queue:
1)if the second stack is not empty, pop an element from the second stack,return
2)if the first stack is not empty, move its elements to the second stack, and pop an element from the second stack, return
3)raise an "empty queue" exception
[time]
push,back operates in O(1), front and pop operates in O(n)
[space]
O(n)
[gist]
https://gist.github.com/A30041839/1b30ac21cefde12e2804

【解题思路】
# solution
# enqueue -- same as the original operation
# dequeue -- use the second stack to store the old element, and pop the oldest one
【时间复杂度】
# for enqueue and isEmpty O(1) in time
# for dequeue O(n) in time
【空间复杂度】
O(n)
【gist link】
https://gist.github.com/zhangjiang2013/7ca3d2df19679845585c

【解题思路】
use one Stack for  Enqueue -----EnQueueStack
* use another Stack for Dequeue----DeQueueStack.
* if DeQueueStack is  empty  then  pop  from EnqueueStack and  push to  DequeueStac one by one.
【时间复杂度】
Enqueue O(1) , Dequeue  O(n)
【空间复杂度】
O(n)
【gist link]
https://gist.github.com/michaelniu/f1cc4577a700db8cc4dd
【test case】
https://gist.github.com/michaelniu/f1cc4577a700db8cc4dd(main)
Code is runnable

【解题思路】
1. naive: using two stack,because queue is FIFO but stack is FILO, when need to pop element, just push every element from si into s2 and then do s2.pop(). The peek() is the same method, after operation, just push every element from s2 back to s1.
2. instead doing reverse operation each time, we can hold two stacks, one is record newStack, the other hold oldStack, when we need to push(), just push newElem onto newStack, when we need to pop,just do pop operation on oldStack,if oldStack is empty, then push elements from newStack to oldStack in reverse order.
【时间复杂度】
Enqueue O(1) , Dequeue  O(n)
【空间复杂度】
O(n)
【gist link]
https://gist.github.com/JamesJi9277/425d9a0b8ae477ab5aaa
【test case】

[solution]
when adding x to the queue, just push it to the first stack.
when removing from the queue:
1)if the second stack is not empty, directly pop from the second stack
2)else if the first stack is not empty, shift all elements to the second stack, and pop from the second stack
3)else throw exception
[time]
add O(1), remove and peek operates in O(n)
[space]
O(n)
[gist]
https://gist.github.com/kelly-us/ca1854a0b3d928a2db46

【解题思路】
建立两个栈，一个做输入栈，一个做输出栈，并使用延迟加载（lazy loading）的思路，即仅当输出栈没有可以取的元素时，才将输入栈的元素压入输出栈
【时间复杂度】
push O(1)
pop 输出栈为空时O(m), m是输入栈内的元素个数，其他时候O(1)
【空间复杂度】
O(m)
【gist link】
https://gist.github.com/alikewmk ... le-3-5-myqueue-java

【解题思路】Use one stack1 as the temporary stack to store the newly pushed elements, use the
        other stack2 to store the oldest elements. Once stack2 is empty, move all elements from
        stack1 to stack 2. pop and peek from stack2, while push new element to stack1.
【时间复杂度】O(1) for push, worst case O(n) for peek and pop
【空间复杂度】O(n)
【gist link] https://github.com/StephenWeiXu/ ... aster/Chap3/3_5.cpp
【test case】(optional，如果觉得比较好，欢迎贴出来分享）