队列和栈面试题（解题思路）

1. 实现一个栈，要求实现Push（出栈）、Pop（入栈）、Min（返回最小值的操作）的时间复杂度为O(1)

思路1：定义一个变量min，每次1号栈入栈时，都更新min值并放入2号栈，则1号数据栈出栈时2号栈的栈顶即为当前栈的最小值。

思路2：直接把1号栈2号栈融为一体，每次同时放两个数进去，一个为数据，一个为当前最小值。

    2.使用两个栈实现一个队列

思路：
     
        分别定义两个栈，1号专门进，2号专门出，进的时候无论1号栈有无数据，直接进，出的时候2号栈有数据就出，没数据时，再把1号栈的数据“倒”进2号，再出。

     3.使用两个队列实现一个栈

思路：两个队列，Q1，Q2。Q1用来插删，Q2只用来缓冲
  
      

    4.元素出栈、入栈顺序的合法性。如入栈的序列（1,2,3,4,5），出栈序列为（4,5,3,2,1）

   思路：定义两个指针分别指向入栈数据与出栈数据，比较他们是否相同然后移动继续比较即可，个人觉得其实画图很容易看出来。

    5.一个数组实现两个栈
 
   思路：两个栈用一个线性表来实现，栈顶相对，缺点：无法扩容。
       有人想到用单双数下标来存两个栈，但这样一个栈一直插一个栈不插就会造成空间浪费。