两个栈实现队列 与 两个队列实现栈

                               两个栈实现队列 与 两个队列实现栈
栈与队列是数据结构中较为重要，面试官提过的一个问题，如何使用两个栈实现一个队列，现在，就将如何使用两个栈实现一个队列以及如何使用两个队列实现一个栈记录下来。
   栈：先进后出；队列；先进先出。

一：两个栈实现队列
实现队列，无非实现其入队与出队的两个动作，下面以分解这两个动作时该进行的操作这一方面来入手，谈谈个人的理解，基本上实现方法有如下几种：
栈1：s1 栈2：s2  队列：q
1  入队：将数据压入s1
出队：s1全部元素倒入s2，s2弹出栈顶元素，然后再将s2全部元素倒入s1
s1始终作为入队时的栈，s2作为中转站，每执行一次入队动作，s1添加一个元素，每执行完一次出队动作，s2保持空的状态。即，只有在出队的过程中，s1向s2倒入元素时，s2才不为空，其余时间s2始终为空。
动作执行示意图：
（1）依次入队1,2,3元素    （2）出队：s1倒入s2，s2弹出栈顶元素  （3）出队完毕，s2倒回s1


每次执行都按照该逻辑，
入队顺序：1,2,3  出队顺序1,2,3，实现队列先进先出

2  入队：判断s1是否为空，若为空元素都在s2中，s2全部元素倒入s1，将入队元素压入s1；若不为空，直接压入s1。
   出队：判断s2是否为空，若为空元素都在s1中，s1全部元素倒入s2，弹出s2栈顶元素；s2不为空，直接弹出栈顶元素。
该种方式相对于第一种方式来说，避免了出队动作完毕后，s2倒回s1这一动作，如果连续执行出队动作，将减小时间复杂度，提高算法的效率。
3  入队：压入s1
   出队：判断s2是否为空，s2为空则将s1全部元素倒入s2，弹出s2栈顶元素；s2不为空，则直接弹出栈顶元素。
相较与第二种方式，减少了入队时s2全部元素倒回s1的这一动作，再一次提高算法效率。

以上三种方式从时间复杂度来说，第三种复杂度最小，效率也最高。三种方式都是以s1做为入队栈，s2作为出队栈，在执行入队与出队动作时，元素在s1与s2之间转换，只是转换的顺序与条件不一样。当然，以上几种方式未考虑栈与队列的大小有限的情况，也未考虑在s1，s2都为空执行出队动作的极端情况。
还有在出队时，s1向s2倒入的时候，可以将s1栈底元素不倒入s2，之后s1保留栈底元素，s2存储其它元素。出队时弹出s1的栈底元素，其实此刻s1只有一个元素。这样虽然减少了一次倒入动作，但是个人认为在n次入队出队动作时，这一次可以忽略不计，而且增加了算法的复杂性，编程实现时代码也更复杂。所以，为了算法的简洁性和编程实现代码的可读性，牺牲一点效率也是值得的。




二：两个队列实现栈
实现栈的入栈和出栈，以先进先出的两个队列实现先进后出的栈，其实其思想和两个队列实现栈大同小异的，总结有以下几种方式。
队列1：q1  队列2：q2  栈：s

1入栈：入q1队列 1,2,3依次入队q1

   出栈：q1除队尾元素，其它都转移到q2；将q1最后一个元素出列；q2转移回q1。
  
在转移元素时需注意队列先进先出的特性，q1转到q2时，队尾元素不能转。最后实现为，进的顺序为1,2,3，出的顺序为1,2,3。

2（1）入栈：入q1队列
出栈：除队尾元素，其它都转移到q2；将q1最后一个元素出列。图示为以上的1,2步。
（2）再一次入栈：判断q1和q2，两者必定一者为空，一者不为空或两者都为空，后者执行（1）中动作，若为前者则将入栈元素压入非空队列中。
    再一次出栈：非空队列作为（1）中的q1，空队列作为（1）中的q2，执行（1）的动作。
（3）再次栈操作，执行（2）。
该方式重点是始终保持至少一个队列为空，元素都必须集中在一个队列中。其中空队列做为中转队列，非空队列做为入出栈队列。入栈时，元素总是添加在非空队列的队尾，出栈时，总是将非空队列除队尾元素外都转移到空队列，再将入出栈队列的队尾元素弹出，这样非空队列（入出栈队列）和空队列（中转队列）交换了，下一次栈操作执行同样的顺序。

3 入栈：压入空队列q1，再将非空队列q2依次转移回q1（两个队列都为空时，入栈元素默认压入q2队列）。
  出栈：直接从非空队列中弹出队首元素。
同上种方式相似，都必须保证两个队列至少有一个为空。