面试的时候，栈和队列经常成对出现，考察。本文包含以下堆栈和队列的考试内容：（1）堆栈的创建（2）队列的创建（3）具有两个堆栈的队列的实现（4）具有两个队列的堆栈的实现（5）设计与minimumfunctionmin()栈要求min、push、pop的时间复杂度为O(1)(6)判断栈的push和pop顺序是否一致1.栈的创建：接下来我们要创建一个以链表的形式堆叠，方便扩展。代码实现：publicclassStack{publicNodehead;公共节点当前；//方法：栈操作publicvoidpush(intdata){if(head==null){head=newNode(data);当前=头部；}else{节点节点=新节点（数据）；node.pre=current;//当前节点将是当前节点的前驱节点current=node;//让当前节点一直指向新加入的节点}}publicNodepop(){if(current==null){returnnull;}节点节点=当前；//当前节点就是我们要弹出的节点current=current.pre;//每弹出一个节点后，current就回退一个return节点；}类节点{int数据；节点前；//我们需要知道当前节点的前一个节点publicNode(intdata){this.data=data;}}publicstaticvoidmain(String[]args){Stackstack=newStack();堆栈.推(1);堆栈.推(2);堆栈.推(3);System.out.println(stack.pop().data);System.out.println(stack.pop().data);System.out.println(stack.pop().data);}}入栈时，第14行和第15行是关键。运行效果：2、队列的创建：队列的创建有两种形式：基于数组结构实现（序列队列），基于链表结构实现（链队列）。接下来，我们以链表的形式创建一个队列。这样的话，队列在扩展的时候会更方便。队列出队时，从头节点head开始。代码实现：入栈时，操作与普通链表添加节点相同；出队时，头节点总是出队。公共类队列{公共节点头；公共节点电流；//方法：向链表中添加一个节点publicvoidadd(intdata){if(head==null){head=newNode(data);当前=头部；}else{curent.next=newNode(data);curent=curent.next;}}//方法：出队操作publicintpop()throwsException{if(head==null){thrownewException("队列为空");}节点节点=头；//节点node就是我们要出队的节点head=head.next;//离队后，头指针向下移动returnnode.data;}类节点{int数据；下一个节点；publicNode(intdata){this.data=data;}}publicstaticvoidmain(String[]args)throwsException{Queuequeue=newQueue();//入队操作for(inti=0;i<5;i++){queue.add(i);}//出队操作System.out.println(queue.pop());System.out.println(queue.pop());系统.out.println(queue.pop());}}运行效果：3、两个栈实现一个队列：思路：栈1用来存元素，栈2用来弹出元素，负负为正。简单点说，现在把数据1、2、3分别放入栈1，然后从栈1出来(3,2,1)放入栈2。然后，从栈2出来的数据(1,2,3)都符合排队的规律，即负数负数为正数。完整版代码实现：importjava.util.Stack;/***smyhvae创建于2015/9/9.*/publicclassQueue{privateStackstack1=newStack<>();//执行输入入队操作的栈privateStackstack2=newStack<>();//执行出队操作的栈//方法：向队列添加入队操作publicvoidpush(intdata){stack1.push(data);}//方法：给队列一个dequeue操作publicintpop()throwsException{if(stack2.empty()){//stack1中的数据放入stack2之前，首先要保证它在stack2中是空的（要么一开始是空的，要么stack2里面的数据出来了），否则出队顺序会乱，容易忘记while(!stack1.empty()){stack2.push(stack1.pop());//将stack1中的数据出栈放入stack2[核心代码]}}if(stack2.empty()){//当stack2为空时，有两种可能：1.一开始，两个栈中的数据都是空的；2.stack2数据用完thrownewException("队列为空");}返回stack2.pop();}publicstaticvoidmain(String[]args)throwsException{Queuequeue=newQueue();queue.push(1);queue.push(2);队列.推送(3);System.out.println(queue.pop());queue.push(4);System.out.println(queue.pop());System.out.println(queue.pop());System.out.println(queue.pop());}}注意第22行和第30行的代码顺序，以及注释，需要仔细理解它们的意思。运行效果：4、两个队列实现一个栈：思路：将1、2、3依次放入队列1，然后最上面的3留在队列1，后面的2、3放入队列2，3出队列1的。此时队列1为空，然后将队列2中的数据全部放入队列1中；将前2个放入队列1，将后面的3个放入队列2。..依次循环。代码实现：importjava.util.ArrayDeque;importjava.util.Queue;/***创建于smyhvae2015/9/9.*/publicclassStack{Queuequeue1=newArrayDeque();队列<整数>queue2=newArrayDeque<整数>();//方法：栈操作publicvoidpush(intdata){queue1.add(data);}//方法：栈操作publicintpop()throwsException{intdata;if(queue1.size()==0){thrownewException("栈为空");}while(queue1.size()!=0){if(queue1.size()==1){data=queue1.poll();while(queue2.size()!=0){//将queue2中的所有数据放入队列1中queue1.add(queue2.poll());返回数据；}}queue2.add(queue1.poll());}thrownewException("Thestackisempty");//不知道这行代码是什么意思}publicstaticvoidmain(String[]args)throwsException{Stackstack=newStack();堆栈.推(1);堆栈.推(2);堆栈.推(3);System.out.println(stack.pop());System.out.println(堆栈.pop());堆栈.推(4);}}运行效果：5、设计一个栈，最小函数min()，要求min、push、pop的时间复杂度为O(1)。min方法的作用是：可以返回栈中的最小值。【微信面试题】常见思路：一般情况下，我们可能会这样想：使用min变量，每增加一个元素就和min元素进行比较。这样就可以保证min存储的是最小值。但是这样的话，就会有一个问题：如果最小的元素被pop出来了，你怎么知道剩下的元素中哪个是最小的元素呢？改进思路：这里需要增加一个辅助栈，用空间换取时间。在辅助栈中，栈顶总是持有当前栈中最小的值。具体如下：在原栈中，每增加一个新元素，就与辅助栈的栈顶元素进行比较。如果新元素较小，则将新元素的值放入辅助栈。如果新元素很大，就复制辅助栈的栈顶元素，放到辅助栈的最顶层；在原始栈中，出栈时，完整代码实现：importjava.util.Stack;/***Createdbysmyhvaeon2015/9/9.*/publicclassMinStack{privateStackstack=new栈<整数>();privateStackminStack=newStack();//辅助栈：栈顶总是保存当前栈的最小元素publicvoidpush(intdata){stack.push(data);//直接向栈中添加数据//需要在辅助栈中进行判断if(minStack.size()==0||datastack=newStack();//这里需要辅助栈for(inti=0,j=0;i0&&stack.peek()==data2[j]){stack.pop();j++;}}返回stack.size()==0;}publicstaticvoidmain(String[]args){Stackstack=newStack();int[]data1={1,2,3,4,5};int[]data2={4,5,3,2,1};int[]data3={4,5,2,3,1};.out.println(sequenseIsPop(data1,data2));System.out.println(sequenseIsPop(data1,data3));}}代码比较简洁，但是也比较难理解，需要仔细理解。运行结果：
