2 queue as 1 stack, 2 stack as 1 queue
另外这个hexo有个bug,经常会说landscape主题找不到,其实我都没有用这个主题,需要推倒hexo根目录上hexo clean一下 再hexo g, hexo d, 估计是tommy513写的有个bug,最后自己也没修复掉,
要是有人能找到问题原因还挺不错的~~~
2个栈边队列,设为A B
入队列: 入A
出队列: 如果|A|>0,pop A 到push B直到A只有一个元素,然后输出A达到先进先出,那么如果A空了,就直接pop B, 如果B也空了
if A 不空: pop A 到push B直到A只有一个元素,然后popA中的这个元素
else if B: 不空,popB
else:
栈已空
感觉出入队列至少有一个O(n)的,不知道有没有O(1),都已经加了空间代价按道理有的。
2个队列变栈,设为A B
入栈:入A
出栈:(还没理清楚,感觉好像挺麻烦的,这个有通用的思路么)
由于队列倒来倒去顺序还是不变,所以比栈操作会更多一些,because pop and push stack can reverse the sequences.
所以队列是这样的,如果A不空,把A n-1个点逐个dequeue然后enqueue到B, 然后出第N个作为pop,如果A空,那么把B n-1 个点dequeue然后enqueue到A,然后第N个作为pop,一定是先看A,如果A空了再看B,因为入”栈”是从A入的
if n=|A|>=1,dequeue A n-1 to B, dequeue A nth element 作为 "pop"
else if |B|>=1 dequeue B n-1 to A, dequeue B nth element 作为 "pop"
else
can not pop as stack empty
这种DS设计逻辑感觉没啥可以总结出的东西,没啥规律,有点靠灵光一现的感觉。。。感觉就是写几个case,然后归纳出一套处理的流程的规则之类的。。。。
现在想清楚了,总结一下,入的话都简单,选定一个例如A。出的时候根据DS 因地制宜,例如2 stack to be queue, 首先一开始如5个,然后”dequeue”, 将A n-1 pop push to B, 然后 pop A as “dequeue”, if “enqueue” 6, 6 should as the last,
so we can not first choose A for dequeue, instead choose B, if B empty, choose A. And must first if A, then else if B, can not effect the sequence to first if B, then else if A as data first into A then to B.so algorithm would be:
stack A B as queue
enqueue: push A
dequeue:
if A not empty, pop A n-1 element to B, pop A nth element as "dequeue" // first would be all into A, as into "stack" or "queue", so element would first be A, then to B
else if B not empty, pop B as "dequeue" //as when A element to B, its sequence reversed and fit for dequeue "first in first out", so directly pop B would be "dequeue"
else
"queue" empty, can not dequeue
queue A B as stack
push: enqueue A
pop: if n=|A|>=1,dequeue A n-1 to B, dequeue A nth element as "pop"// as first into A
else if |B|>=1 dequeue B n-1 to A, dequeue B nth element as "pop"// queue is first in first out, and dequeue then enqueue would not effect its sequence
else
can not pop as "stack" empty