【第三轮】6.30-7.6 CareerCup 3.5

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


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

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

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

【解题思路】
Implement class API in a similar way as the c++ queue class.
use stackIn to store incoming data, stackOut to pop data. Move all data from stackIn to stackOut in a FILO manner when stackOut runs empty. Update first and last element each time we push or pop (which is the only tricky part in this problem).
【时间复杂度】
O(1) for push
O(N) for pop when data moving is necessary
【空间复杂度】
O(N)
【gist link】
formatting...占坑……
【test case】
(0) -> push(1) -> pop(0) -> push(1) -> push(2) -> pop(1) -> push(2) -> push(3) -> pop(2) -> pop(1) -> pop(0) -> pop(0, error)

【解题思路】
本来是比较简单的问题，我为了记录first and last element额外纠结了很多东西…各种debug完以后什么也不想再写了……
一切尽在comments中，最新版已经把first last那些去掉了，可以在revision history里看到……
（其实我只是饿了噗嗤而且之前发的一篇贴莫名其妙消失了TT）
【时间复杂度】
O(1) for push
O(N) for pop
【空间复杂度】
O(N)
【gist link】
https://gist.github.com/40b53ce17164e2126777
【test case】
(0)->push(1)->pop(0)->push(1)->push(2)->pop(1)->push(2)->push(3)->pop(2)->pop(1)->pop(0)->pop(0,error)

【解题思路】
using two stacks stackIn and stackOut to push/pop elements
push: stackIn.push
pop: if stackOut is empty, move all elements of stackIn into stackOut
size: stackIn.size + stackOut.size
back: stackIn.peek, if stackIn is empty, move all elements of stackOut into stackIn
front: stack.Out.peek, if stackOut is empty, move all elements of stackIn into stackOut
【时间复杂度】O(1) or O(n) (if the stack is empty)
【空间复杂度】O(N)
https://gist.github.com/weazord/f231350faa96658a1016

【解题思路】
用两个stack，一个专门供enqueue （记做pushStack），一个专门用来dequeue （popStack），每次enqueue，直接把元素push进pushStack，每次dequeue，优先从popStack中pop元素，如果没有元素，就将pushStack中的元素全部pop进popStack，再pop元素。
【时间复杂度】
enqueue： O(1)
dequeue：average O(1)
【空间复杂度】
O(n)
【gist link】
https://gist.github.com/chouclee/9fb80a96222d8b8f9d53

【解题思路】
use a stack to push data, use a stack to pop data.
【时间复杂度】
push: O(1)
pop: O(n)
【空间复杂度】
O(n)
【gist link】
https://gist.github.com/qianhuang/061661593396c1ee9602

qianhuang 发表于 2014-7-2 11:15
【解题思路】
use a stack to push data, use a stack to pop data.
when we push(), if all data are i ...

I don't understand why you push the data in 'out' stack back in 'in' stack when pushing new data in 'in' stack. These works are redundant.

ryancooper 发表于 2014-7-2 12:08
I don't understand why you push the data in 'out' stack back in 'in' stack when pushing new data i ...

you are right. Thank you for suggestion.

qianhuang 发表于 2014-7-1 22:15
【解题思路】
use a stack to push data, use a stack to pop data.
【时间复杂度】

I assume your pop() function doesn't have return value, then how would you get the top element value since you don't have a top() function to keep track of it? It seems to me that you're only popping things out while losing information about them, and that's not the way queue works....

【解题思路】
Divide queue into two stacks, whose top element is head and tail of the queue

【时间复杂度】
O(1)

【空间复杂度】
O(1) amortized cost

【gist link】
https://gist.github.com/chrislukkk/6a9f88001b172ba629ed

ivycheung1208 发表于 2014-7-3 05:19
I assume your pop() function doesn't have return value, then how would you get the top element val ...

thank you for review.
PS: 怎么点评别人的帖子？我找不到这功能？