《栈与队列数据结构的“双生花”》一.栈:后进先出1.1认识栈这一章的栈和队列比较简单;1.2后进先出1.3基于数组的栈模拟①.入栈②.出栈③.取栈顶元素二.队列:先进先出2.1认识队列注意:队列他是接口,接口,接口!2.2队列图解2.3 以数组模拟队列①入队列②.出队列③.取队首元素2.4以链表模拟队列①入队列②出队列③取队首元素三.栈和队列题目1. 括号匹配2. 逆波兰表达式求值3. 出栈入栈次序匹配4. 最小栈四.面试题1. 用队列实现栈。2. 用栈实现队列。一.栈:后进先出1.1认识栈这一章的栈和队列比较简单;首先是:后进先出的栈我们可以把栈理解为简化版的顺序表,他最主要的就是三个操作:①入栈------尾插②出栈------尾删③取栈顶元素栈的方法:入栈:push();出栈:pop();取栈顶元素:peek();1.2后进先出后进先出,这个不难理解,就是后入栈的元素,进行出栈或者取栈顶元素时,先处来,俗话说枪打出头鸟,后来者机会大,这就是后进先出;代码演示://实例化栈StackIntegerstacknewStack();//注意这种引用类型存储的变量要写成包装类型;//入栈stack.push(1);stack.push(2);stack.push(3);stack.push(4);//出栈intastack.pop();//这里是4;System.out.println(a);//4//取栈顶元素System.out.println(stack.peek());//这里是31.3基于数组的栈模拟①.入栈classMyArrayStack{//首先创集一个数组privateint[]data;privateintsize;publicMyArrayStack(intsize){this.datanewint[size];}publicMyArrayStack(){this.datanewint[10];}privatevoidgrow(){int[]Edatanewint[2*data.length];for(inti0;idata.length;i){Edata[i]data[i];}dataEdata;}//入栈模拟publicvoidpush(intval){if(data.lengthsize){grow();}data[size]val;size;}}②.出栈publicintpop(){if(size0)thrownewRuntimeException(栈为空);//size先减减,扩容减一,然后返回栈顶元素returndata[--size];}③.取栈顶元素publicintpeek(){if(size0)thrownewRuntimeException(栈为空);returndata[size-1];}二.队列:先进先出2.1认识队列队列与栈不同,他是先进先出,也就是先入队列的元素先出来,后来的慢慢排队,这个在我们日常生活中是很常见的,比如排队吃饭,肯定是先排在前面的先吃到饭,后排的后吃饭;队列方法:注意:队列他是接口,接口,接口!这里我只说链表实现了这个接口,这是最常见,最常用的的向上转型,其他的以后再说;//用链表的向上转型QueueIntegerqueuenewLinkedList();queue.offer(1);queue.offer(2);queue.offer(3);intbqueue.poll();//1System.out.println(b);//打印出先进去的12.2队列图解队列我们也是要掌握三种基本操作:入队列,出队列,取队首元素;入队列-----尾插出队列-----头删取队首元素2.3 以数组模拟队列这里我们用不一样的方法,之前我们在写入栈方法时,他是属于动态内存,用完了,可以直接继续不断地扩容,这次我们用固定数组首先创建头标head,尾标tail;publicclassMyArrayQueue{publicint[]data;publicinthead0;publicinttail0;publicintsize0;publicMyArrayQueue(intcount){this.datanewint[count];}publicMyArrayQueue(){this.datanewint[10];}}①入队列publicvoidoffer(intval){if(sizedata.length){return;//直接结束}if(taildata.length){tail0;}data[tail]val;size;}②.出队列publicIntegerpoll(){if(size0){returnnull;}intresdata[head];head;if(headdata.length){head0;}size--;returnres;}③.取队首元素publicIntegerpeek(){if(size0){returnnull;}returndata[head];}2.4以链表模拟队列首先创建链表节点;classELinkedNode{publicintval;publicELinkedNodenext;publicELinkedNode(intval){this.valval;this.nextnull;}}①入队列publicclassMyLinkedQueue{ELinkedNodeheadnull;ELinkedNodetailnull;publicvoidoffer(intval){ELinkedNodenewNodenewELinkedNode(val);if(headnull){tailnewNode;headnewNode;return;}tail.nextnewNode;tailtail.next;}}②出队列publicIntegerpoll(){if(headnull){returnnull;}ELinkedNodecurhead;headhead.next;returncur.val;}③取队首元素publicIntegerpeek(){if(headnull){returnnull;}returnhead.val;}三.栈和队列题目1. 括号匹配括号匹配题目分析1).首先判断符号十分时左括号,如果说,直接入栈2).还需要判断是否右括号,不然直接返回false;3).最后依次出栈与右括号比较是否配对4)返回栈是否为空.为空左右括号都匹配到了publicbooleanisMatch(charstr1,charstr2){if(str1(str2)){returntrue;}if(str1[str2]){returntrue;}if(str1{str2}){returntrue;}returnfalse;}publicbooleanisValid(Strings){StackCharacterstacknewStack();for(inti0;is.length();i){charchs.charAt(i);if(ch(||ch[||ch{){stack.push(ch);continue;}if(ch!)ch!}ch!]){returnfalse;}if(stack.empty()){returnfalse;}charstrstack.peek();if(isMatch(str,ch)){stack.pop();continue;}returnfalse;}returnstack.empty();}2. 逆波兰表达式求值逆波兰表达式求值题目解析1.首先判断是否为数字如果是直接入栈2.数字和符号都不是continue,这个题其实不用考虑但我们还是要写全部3).接着判断是加减乘除拿出两个元素进行计算publicbooleanisnumber(Stringstr){if(str.equals()||str.equals(-)||str.equals(*)||str.equals(/)){returnfalse;}returntrue;}publicintevalRPN(String[]tokens){StackIntegerstacknewStack();for(Stringstr:tokens){if(isnumber(str)){stack.push(Integer.parseInt(str));continue;}if(!stack.empty()){intres0;intbstack.pop();intastack.pop();if(str.equals()){resab;}if(str.equals(-)){resa-b;}if(str.equals(*)){resa*b;}if(str.equals(/)){resa/b;}stack.push(res);}}returnstack.pop();}3. 出栈入栈次序匹配栈的压入、弹出序列题目解析1.创建一个栈原来入栈2遍历入栈数组先入栈循环判断是否不为空3.如果相等直接出栈出栈数组往后遍历加14.如果不相等直接结束此次循环5.返回栈是否为空publicbooleanIsPopOrder(int[]pushV,int[]popV){// write code hereStackIntegerstacknewStack();intsizepushV0;intsizepopV0;for(;sizepushVpushV.length;sizepushV){stack.push(pushV[sizepushV]);while(!stack.empty()){if(stack.peek()popV[sizepopV]){stack.pop();sizepopV;}else{break;}}}returnstack.empty();}4. 最小栈最小栈可以看到给了一个构造方法用来初始化,然后四个操作方法;题目解析:1)首先定义两个栈 ,一个用来正常存储原数据,一个用来存储最小元素的栈publicMinStack(){privateStackIntegerstacknewStack();privateStackIntegerminstacknewStack();}2)判断,数值每次存储在satack,如果最小栈为空,存储value;不断比较min最小值来更新,最后入栈minpublicvoidpush(intvalue){stack.push(value);if(minstack.empty()){minstack.push(value);return;}intminminstack.peek();if(valuemin){minvalue;}else{minmin;}minstack.push(min);}3)出栈publicvoidpop(){stack.pop();minstack.pop();}4)取栈顶元素publicinttop(){returnstack.peek();}5)取最下栈顶元素publicintgetMin(){returnminstack.peek();}四.面试题1. 用队列实现栈。用队列实现栈1).首先关键是出栈和去栈;2).我们需要准备两个队列,一个用来存储元素,当出栈时,将A中的元素不断循环遍历倒腾到B,只剩一个元素就可以出栈了,达到了栈的出栈;3)取栈顶元素与出栈差不多,只不过多加了一个把最后一个元素还是要倒腾到B中;classMyStack{publicQueueIntegerAnewLinkedList();publicQueueIntegerBnewLinkedList();publicMyStack(){}publicbooleanempty(){returnA.isEmpty()B.isEmpty();}publicvoidswapAB(){QueueIntegertempnewLinkedList();tempA;AB;Btemp;}publicvoidpush(intx){A.offer(x);}publicintpop(){if(empty()){return0;}while(A.size()1){IntegercurA.poll();B.offer(cur);}IntegerresA.poll();swapAB();returnres;}publicinttop(){if(empty()){return0;}while(A.size()1){IntegercurA.poll();B.offer(cur);}IntegerresA.poll();B.offer(res);swapAB();returnres;}}2. 用栈实现队列。用栈实现队列题目解析:1)首先创建两个栈,A用来入队列,B用来出队列;2)检查B是否为空,如果不为空,首先将B的元素倒腾到A里面去,然后再对A进行入栈操作;3)出栈时遵循后进先出,依次将A中的元素入到B中,B中采用后进先出,此时就达到队列的作用