Java模拟栈和队列数据结构的基本示例讲解
栈和队列:
一般是作为程序员的工具,用于辅助构思算法,生命周期较短,运行时才被创建;
访问受限,在特定时刻,只有一个数据可被读取或删除;
是一种抽象的结构,内部的实现机制,对用户不可见,比如用数组、链表来实现栈。
模拟栈结构
同时,只允许一个数据被访问,后进先出
对于入栈和出栈的时间复杂度都为O(1),即不依赖栈内数据项的个数,操作比较快
例,使用数组作为栈的存储结构
publicclassStackS<T>{ privateintmax; privateT[]ary; privateinttop;//指针,指向栈顶元素的下标 publicStackS(intsize){ this.max=size; ary=(T[])newObject[max]; top=-1; } //入栈 publicvoidpush(Tdata){ if(!isFull()) ary[++top]=data; } //出栈 publicTpop(){ if(isEmpty()){ returnnull; } returnary[top--]; } //查看栈顶 publicTpeek(){ returnary[top]; } //栈是否为空 publicbooleanisEmpty(){ returntop==-1; } //栈是否满 publicbooleanisFull(){ returntop==max-1; } //size publicintsize(){ returntop+1; } publicstaticvoidmain(String[]args){ StackS<Integer>stack=newStackS<Integer>(3); for(inti=0;i<5;i++){ stack.push(i); System.out.println("size:"+stack.size()); } for(inti=0;i<5;i++){ Integerpeek=stack.peek(); System.out.println("peek:"+peek); System.out.println("size:"+stack.size()); } for(inti=0;i<5;i++){ Integerpop=stack.pop(); System.out.println("pop:"+pop); System.out.println("size:"+stack.size()); } System.out.println("----"); for(inti=5;i>0;i--){ stack.push(i); System.out.println("size:"+stack.size()); } for(inti=5;i>0;i--){ Integerpeek=stack.peek(); System.out.println("peek:"+peek); System.out.println("size:"+stack.size()); } for(inti=5;i>0;i--){ Integerpop=stack.pop(); System.out.println("pop:"+pop); System.out.println("size:"+stack.size()); } } }
上面的例子,有一个maxSize的规定,因为数组是要规定大小的,若想无限制,可以使用其他结构来做存储,当然也可以new一个新的长度的数组。
例,使用LinkedList存储来实现栈
publicclassStackSS<T>{ privateLinkedList<T>datas; publicStackSS(){ datas=newLinkedList<T>(); } //入栈 publicvoidpush(Tdata){ datas.addLast(data); } //出栈 publicTpop(){ returndatas.removeLast(); } //查看栈顶 publicTpeek(){ returndatas.getLast(); } //栈是否为空 publicbooleanisEmpty(){ returndatas.isEmpty(); } //size publicintsize(){ returndatas.size(); } publicstaticvoidmain(String[]args){ StackS<Integer>stack=newStackS<Integer>(3); for(inti=0;i<5;i++){ stack.push(i); System.out.println("size:"+stack.size()); } for(inti=0;i<5;i++){ Integerpeek=stack.peek(); System.out.println("peek:"+peek); System.out.println("size:"+stack.size()); } for(inti=0;i<5;i++){ Integerpop=stack.pop(); System.out.println("pop:"+pop); System.out.println("size:"+stack.size()); } System.out.println("----"); for(inti=5;i>0;i--){ stack.push(i); System.out.println("size:"+stack.size()); } for(inti=5;i>0;i--){ Integerpeek=stack.peek(); System.out.println("peek:"+peek); System.out.println("size:"+stack.size()); } for(inti=5;i>0;i--){ Integerpop=stack.pop(); System.out.println("pop:"+pop); System.out.println("size:"+stack.size()); } } }
例,单词逆序,使用Statck结构
publicclassWordReverse{ publicstaticvoidmain(String[]args){ reverse("株式会社"); } staticvoidreverse(Stringword){ if(word==null)return; StackSS<Character>stack=newStackSS<Character>(); char[]charArray=word.toCharArray(); intlen=charArray.length; for(inti=0;i<len;i++){ stack.push(charArray[i]); } StringBuildersb=newStringBuilder(); while(!stack.isEmpty()){ sb.append(stack.pop()); } System.out.println("反转后:"+sb.toString()); } }
打印:
反转后:社会式株
模拟队列(一般队列、双端队列、优先级队列)
队列:
先进先出,处理类似排队的问题,先排的,先处理,后排的等前面的处理完了,再处理
对于插入和移除操作的时间复杂度都为O(1),从后面插入,从前面移除
双端队列:
即在队列两端都可以insert和remove:insertLeft、insertRight,removeLeft、removeRight
含有栈和队列的功能,如去掉insertLeft、removeLeft,那就跟栈一样了;如去掉insertLeft、removeRight,那就跟队列一样了
一般使用频率较低,时间复杂度O(1)
优先级队列:
内部维护一个按优先级排序的序列。插入时需要比较查找插入的位置,时间复杂度O(N),删除O(1)
/* *队列先进先出,一个指针指示插入的位置,一个指针指示取出数据项的位置 */ publicclassQueueQ<T>{ privateintmax; privateT[]ary; privateintfront;//队头指针指示取出数据项的位置 privateintrear;//队尾指针指示插入的位置 privateintnItems;//实际数据项个数 publicQueueQ(intsize){ this.max=size; ary=(T[])newObject[max]; front=0; rear=-1; nItems=0; } //插入队尾 publicvoidinsert(Tt){ if(rear==max-1){//已到实际队尾,从头开始 rear=-1; } ary[++rear]=t; nItems++; } //移除队头 publicTremove(){ Ttemp=ary[front++]; if(front==max){//列队到尾了,从头开始 front=0; } nItems--; returntemp; } //查看队头 publicTpeek(){ returnary[front]; } publicbooleanisEmpty(){ returnnItems==0; } publicbooleanisFull(){ returnnItems==max; } publicintsize(){ returnnItems; } publicstaticvoidmain(String[]args){ QueueQ<Integer>queue=newQueueQ<Integer>(3); for(inti=0;i<5;i++){ queue.insert(i); System.out.println("size:"+queue.size()); } for(inti=0;i<5;i++){ Integerpeek=queue.peek(); System.out.println("peek:"+peek); System.out.println("size:"+queue.size()); } for(inti=0;i<5;i++){ Integerremove=queue.remove(); System.out.println("remove:"+remove); System.out.println("size:"+queue.size()); } System.out.println("----"); for(inti=5;i>0;i--){ queue.insert(i); System.out.println("size:"+queue.size()); } for(inti=5;i>0;i--){ Integerpeek=queue.peek(); System.out.println("peek:"+peek); System.out.println("size:"+queue.size()); } for(inti=5;i>0;i--){ Integerremove=queue.remove(); System.out.println("remove:"+remove); System.out.println("size:"+queue.size()); } } }
/* *双端队列<spanstyle="white-space:pre"></span>两端插入、删除 */ publicclassQueueQT<T>{ privateLinkedList<T>list; publicQueueQT(){ list=newLinkedList<T>(); } //插入队头 publicvoidinsertLeft(Tt){ list.addFirst(t); } //插入队尾 publicvoidinsertRight(Tt){ list.addLast(t); } //移除队头 publicTremoveLeft(){ returnlist.removeFirst(); } //移除队尾 publicTremoveRight(){ returnlist.removeLast(); } //查看队头 publicTpeekLeft(){ returnlist.getFirst(); } //查看队尾 publicTpeekRight(){ returnlist.getLast(); } publicbooleanisEmpty(){ returnlist.isEmpty(); } publicintsize(){ returnlist.size(); } }
/* *优先级队列队列中按优先级排序,是一个有序的队列 */ publicclassQueueQP{ privateintmax; privateint[]ary; privateintnItems;//实际数据项个数 publicQueueQP(intsize){ this.max=size; ary=newint[max]; nItems=0; } //插入队尾 publicvoidinsert(intt){ intj; if(nItems==0){ ary[nItems++]=t; }else{ for(j=nItems-1;j>=0;j--){ if(t>ary[j]){ ary[j+1]=ary[j];//前一个赋给后一个小的在后相当于用了插入排序,给定序列本来就是有序的,所以效率O(N) }else{ break; } } ary[j+1]=t; nItems++; } System.out.println(Arrays.toString(ary)); } //移除队头 publicintremove(){ returnary[--nItems];//移除优先级小的 } //查看队尾优先级最低的 publicintpeekMin(){ returnary[nItems-1]; } publicbooleanisEmpty(){ returnnItems==0; } publicbooleanisFull(){ returnnItems==max; } publicintsize(){ returnnItems; } publicstaticvoidmain(String[]args){ QueueQPqueue=newQueueQP(3); queue.insert(1); queue.insert(2); queue.insert(3); intremove=queue.remove(); System.out.println("remove:"+remove); } }