初级--04---链表反转----链表实现、栈、队列、双端队列

提示文章写完后目录可以自动生成如何生成可参考右边的帮助文档文章目录链表反转**Node 节点**单链表反转双链表反转单链表实现-----队列线性表--07---队列代码对数器单链表实现-----栈线性表--05---栈代码对数器双端队列代码对数器链表反转Node 节点publicstaticclassNode{publicintvalue;publicNodenext;publicNode(intdata){valuedata;}}publicstaticclassDoubleNode{publicintvalue;publicDoubleNodelast;publicDoubleNodenext;publicDoubleNode(intdata){valuedata;}}单链表反转publicstaticNodereverseLinkedList(Nodehead){Nodeprenull;Nodenextnull;while(head!null){nexthead.next;head.nextpre;prehead;headnext;}returnpre;}双链表反转publicstaticDoubleNodereverseDoubleList(DoubleNodehead){DoubleNodeprenull;DoubleNodenextnull;while(head!null){nexthead.next;head.nextpre;head.lastnext;prehead;headnext;}returnpre;单链表实现-----队列线性表–07—队列代码publicstaticclassNodeV{publicVvalue;publicNodeVnext;publicNode(Vv){valuev;nextnull;}}publicstaticclassMyQueueV{privateNodeVhead;privateNodeVtail;privateintsize;publicMyQueue(){headnull;tailnull;size0;}publicbooleanisEmpty(){returnsize0;}publicintsize(){returnsize;}publicvoidoffer(Vvalue){NodeVcurnewNodeV(value);if(tailnull){headcur;tailcur;}else{tail.nextcur;tailcur;}size;}// C/C的同学需要做节点析构的工作publicVpoll(){Vansnull;if(head!null){anshead.value;headhead.next;size--;}if(headnull){tailnull;}returnans;}// C/C的同学需要做节点析构的工作publicVpeek(){Vansnull;if(head!null){anshead.value;}returnans;}}对数器publicstaticvoidtestQueue(){MyQueueIntegermyQueuenewMyQueue();QueueIntegertestnewLinkedList();inttestTime5000000;intmaxValue200000000;System.out.println(测试开始);for(inti0;itestTime;i){if(myQueue.isEmpty()!test.isEmpty()){System.out.println(Oops!);}if(myQueue.size()!test.size()){System.out.println(Oops!);}doubledecideMath.random();if(decide0.33){intnum(int)(Math.random()*maxValue);myQueue.offer(num);test.offer(num);}elseif(decide0.66){if(!myQueue.isEmpty()){intnum1myQueue.poll();intnum2test.poll();if(num1!num2){System.out.println(Oops!);}}}else{if(!myQueue.isEmpty()){intnum1myQueue.peek();intnum2test.peek();if(num1!num2){System.out.println(Oops!);}}}}if(myQueue.size()!test.size()){System.out.println(Oops!);}while(!myQueue.isEmpty()){intnum1myQueue.poll();intnum2test.poll();if(num1!num2){System.out.println(Oops!);}}System.out.println(测试结束);}单链表实现-----栈线性表–05—栈代码publicstaticclassNodeV{publicVvalue;publicNodeVnext;publicNode(Vv){valuev;nextnull;}}publicstaticclassMyStackV{privateNodeVhead;privateintsize;publicMyStack(){headnull;size0;}publicbooleanisEmpty(){returnsize0;}publicintsize(){returnsize;}publicvoidpush(Vvalue){NodeVcurnewNode(value);if(headnull){headcur;}else{cur.nexthead;headcur;}size;}publicVpop(){Vansnull;if(head!null){anshead.value;headhead.next;size--;}returnans;}publicVpeek(){returnhead!null?head.value:null;}}对数器publicstaticvoidtestStack(){MyStackIntegermyStacknewMyStack();StackIntegertestnewStack();inttestTime5000000;intmaxValue200000000;System.out.println(测试开始);for(inti0;itestTime;i){if(myStack.isEmpty()!test.isEmpty()){System.out.println(Oops!);}if(myStack.size()!test.size()){System.out.println(Oops!);}doubledecideMath.random();if(decide0.33){intnum(int)(Math.random()*maxValue);myStack.push(num);test.push(num);}elseif(decide0.66){if(!myStack.isEmpty()){intnum1myStack.pop();intnum2test.pop();if(num1!num2){System.out.println(Oops!);}}}else{if(!myStack.isEmpty()){intnum1myStack.peek();intnum2test.peek();if(num1!num2){System.out.println(Oops!);}}}}if(myStack.size()!test.size()){System.out.println(Oops!);}while(!myStack.isEmpty()){intnum1myStack.pop();intnum2test.pop();if(num1!num2){System.out.println(Oops!);}}System.out.println(测试结束);}双端队列代码publicstaticclassNodeV{publicVvalue;publicNodeVlast;publicNodeVnext;publicNode(Vv){valuev;lastnull;nextnull;}}publicstaticclassMyDequeV{privateNodeVhead;privateNodeVtail;privateintsize;publicMyDeque(){headnull;tailnull;size0;}publicbooleanisEmpty(){returnsize0;}publicintsize(){returnsize;}publicvoidpushHead(Vvalue){NodeVcurnewNode(value);if(headnull){headcur;tailcur;}else{cur.nexthead;head.lastcur;headcur;}size;}publicvoidpushTail(Vvalue){NodeVcurnewNode(value);if(headnull){headcur;tailcur;}else{tail.nextcur;cur.lasttail;tailcur;}size;}publicVpollHead(){Vansnull;if(headnull){returnans;}size--;anshead.value;if(headtail){headnull;tailnull;}else{headhead.next;head.lastnull;}returnans;}publicVpollTail(){Vansnull;if(headnull){returnans;}size--;anstail.value;if(headtail){headnull;tailnull;}else{tailtail.last;tail.nextnull;}returnans;}publicVpeekHead(){Vansnull;if(head!null){anshead.value;}returnans;}publicVpeekTail(){Vansnull;if(tail!null){anstail.value;}returnans;}}对数器publicstaticvoidtestDeque(){MyDequeIntegermyDequenewMyDeque();DequeIntegertestnewLinkedList();inttestTime5000000;intmaxValue200000000;System.out.println(测试开始);for(inti0;itestTime;i){if(myDeque.isEmpty()!test.isEmpty()){System.out.println(Oops!);}if(myDeque.size()!test.size()){System.out.println(Oops!);}doubledecideMath.random();if(decide0.33){intnum(int)(Math.random()*maxValue);if(Math.random()0.5){myDeque.pushHead(num);test.addFirst(num);}else{myDeque.pushTail(num);test.addLast(num);}}elseif(decide0.66){if(!myDeque.isEmpty()){intnum10;intnum20;if(Math.random()0.5){num1myDeque.pollHead();num2test.pollFirst();}else{num1myDeque.pollTail();num2test.pollLast();}if(num1!num2){System.out.println(Oops!);}}}else{if(!myDeque.isEmpty()){intnum10;intnum20;if(Math.random()0.5){num1myDeque.peekHead();num2test.peekFirst();}else{num1myDeque.peekTail();num2test.peekLast();}if(num1!num2){System.out.println(Oops!);}}}}if(myDeque.size()!test.size()){System.out.println(Oops!);}while(!myDeque.isEmpty()){intnum1myDeque.pollHead();intnum2test.pollFirst();if(num1!num2){System.out.println(Oops!);}}System.out.println(测试结束);}