栈与队列的应用扩展

利用两个栈实现一个队列

思路： 队列的性质是先进先出，栈是先进后出。 如果利用两个栈实现队列，那么我们如果能把第一个栈倒置进第二个栈，第二个栈顶出栈，不就是出队了么。

利用这个思路，我们定义两个栈（s1,s2），一个存储数据(s1)，一个辅助出队(s2)。

入队：就是进栈 出队：先把s1倒置进s2，s2出栈 也就是不断的给s2.push(s1.pop);直到s1为空时停止 然后保存s2的栈顶元素，同时s2出栈，我们再把s2倒置回s1，保证队列数据的正确性。 s1倒置进s2，保存s2栈顶元素并出栈。

倒置回去 最终结果：

实现：

public class stackExt1<E> { protected Stack<E> s1; protected Stack<E> s2; stackExt1(){ s1 = new Stack<>(); s2 = new Stack<>(); } //入队 public void push(E data){ s1.push(data); } //出队 public E pop(){ while(!s1.isEmpty()) { //将s1倒置进s2 s2.push(s1.pop()); } E result = s2.pop(); //将s2的栈顶元素，也就是入队的第一个元素，保存并出栈 while(!s2.isEmpty()){ s1.push(s2.pop()); //倒置回去 } return result; } public void show(){ //借用s2按照顺序打印元素 while(!s1.isEmpty()){ s2.push(s1.pop()); //先倒置入栈s2 } //倒置回去 while(!s2.isEmpty()) { System.out.print(s2.peek() + " "); //挨个打印栈顶，倒置回去 s1.push(s2.pop()); } System.out.println(); } }

利用两个队列实现一个栈

思路： 队列是先进先出，如果要先进后出， 就先让队尾之前的元素进入另一个队列，这时队尾就成为了队头，出队时就成为了后进先出，队尾出队之后，队尾之前的元素再入队回来，保证数据的完整和正确性。

入栈：与入队一样

出队：

实现：

//利用两个队列实现一个栈 public class stackExt2 <E>{ protected LinkedList<E> Q1; //底层实现队列是基于LinkedList protected LinkedList<E> Q2; // add() 入队 remove() 出队 size() 有效个数 stackExt2(){ Q1 = new LinkedList<>(); Q2 = new LinkedList<>(); } //入栈 public void push(E data){ Q1.add(data); } //出栈 public E pop() { while (Q1.size() != 1) { //将Q1队列除了队尾元素 入队Q2 Q2.add(Q1.remove()); } E result = Q1.remove(); //保存队尾值（栈顶） while(Q2.size() != 0){ //将Q2倒置回Q1 Q1.add(Q2.remove()); } return result; } //打印栈元素 public void show(){ while(Q1.size() != 0){ System.out.print(Q1.getFirst()+" "); Q2.add(Q1.remove()); } while(Q2.size() != 0){ Q1.add(Q2.remove()); } System.out.println(); } }

栈中实现min方法，保证push、pop、min时间复杂度都是O(1)

min（）就是输出当前栈中的最小值

思路： 首先我们要思考如果不选择遍历寻找，怎么样才能让时间复杂度为O(1); 其次，怎么样才能让min方法的每一次输出都是当前栈的最小值

根据这两个思想和stack（栈）的属性，如果要让时间复杂度为O（1），只能选择出栈，因为stack并没有给我们 Index 下标属性，并且就算我们自己创造一个属性，那么如果是在栈内，我们还是需要移动这个值到栈顶的所有元素，依旧无法保证时间复杂度。 那么我们就保存每一次入栈之后，这个栈的最小值，将它保存到一个辅助栈当中，当要获取这个栈的最小值时，min.peek（）就可以了！当我们的数据栈出栈时，我们的辅助站（min）也出栈，这时min的栈顶，就是当前数据栈中的最小值。

图例：

实现：

public class stackExt3<E extends Comparable> { protected Stack<E> s1; protected Stack<E> s2; E min; //保存当前数据栈的最小值 stackExt3(){ s1 = new Stack<>(); s2 = new Stack<>(); } //入栈 public void push(E data){ if(s1.isEmpty()){ min = data; //如果栈为空，那么这时入栈的元素，也就是第一个元素，就是最小值 } else { if (min.compareTo(data) > 0) { //如果栈不为空，并且 min 比 入栈的元素（data） 大 min = data; //那么将data 赋给 min } } s1.push(data); //数据栈入栈元素 s2.push(min); //辅助栈入栈当前栈的最小值 } //出栈 public E pop(){ s2.pop(); //辅助栈也要出栈 return s1.pop(); } //获取当前栈的最小值 public E mindata(){ return s2.peek(); } }

两个序列，入栈序列为1， 出栈序列为2， 判断2是否是1的出栈序列

举个例子，入栈序列为 1 2 3 4 5；出栈序列为 4 5 3 2 1，这个出栈序列是否是这个入栈序列的合法出栈序列呢？

首先我们先按照我们的思想判断一个出栈序列是不是对应这个入栈顺序。

那么 5 4 2 3 1是不是对应的入栈顺序呢呢？

1入 2入 3入 4入 5入 5出 4出 2出

我们发现，3才是栈顶 2是出不了栈的，所以我们就出不了栈。

那么 2 3 1 4 5 是不是出栈顺序？ 1入 2 入 2出 3入 3出 1出 4入 4出 5入 5出

首先我们可以抽象出，出栈序列出的永远是当前栈的栈顶，假如入栈顺序是 1 2 3 4 5，如果出栈顺序第一个数字是 5 。 那么1 2 3 4 5必须全部入栈才行，如果出栈顺序第一个数字是 4 。那么1 2 3 4 必须全部入栈才行。

其次，可以边入栈边出栈的。

所以每一次入栈，我们都要判断一下，这个栈顶元素是否是出栈序列的第一个元素

如果找到了第一个元素，那么我们就出栈，并且判断当前栈顶，是否是出栈序列的第二个元素，

如果是，接着出栈，判断栈顶是否是出栈序列的第三个元素

如果不是，那么我们就入栈，在判断这个栈顶是否是第三个元素，如果不是，接着入栈，入到没有元素可入为止，如果还没有找到，那么就不是出栈序列，因为出栈序列的某个值 只可能是 栈顶元素或者未入栈的元素，如果都没有找到，那么就证明它不符合顺序。 也就是到最后栈不为空，就不符合入栈顺序。

实现：

public static boolean sequenceCorrect(int [] push,int [] pop){ if(push.length == 0 &&push == null && pop.length == 0 && pop == null){ return false; } //先创建一个辅助栈 Stack<Integer> s1 = new Stack(); int j = 0 ; //出栈序列的第 j 个元素 for(int i = 0 ;i < push.length; i++){ //按顺序压入辅助栈 s1.push(push[i]); while(!s1.isEmpty() && s1.peek() == pop[j] ) { //如果辅助栈为空，证明已经出完 //如果相同，那么就出栈，同时j++。接着对比栈顶和pop[j] s1.pop(); j++; } } return s1.isEmpty(); //如果剩余元素，则顺序不对，那么就不为空 }