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

Posted by richard爱闹 - 7月 12 2014
如需转载,请注明: 本文来自 Richard