Java实现栈和队列

本文内容纲要：

栈：LIFO（后进先出）

队列：FIFO（先进先出）

栈的顺序存储结构实现：

/** *基于数组实现的顺序栈 *@param<E> */ publicclassStack<E>{ privateObject[]data=null; privateintmaxSize=0;//栈容量 privateinttop=-1;//栈顶指针 /** *构造函数：根据给定的size初始化栈 */ Stack(){ this(10);//默认栈大小为10 } Stack(intinitialSize){ if(initialSize>=0){ this.maxSize=initialSize; data=newObject[initialSize]; top=-1; }else{ thrownewRuntimeException("初始化大小不能小于0："+initialSize); } } //判空 publicbooleanempty(){ returntop==-1?true:false; } //进栈,第一个元素top=0； publicbooleanpush(Ee){ if(top==maxSize-1){ thrownewRuntimeException("栈已满，无法将元素入栈！"); }else{ data[++top]=e; returntrue; } } //查看栈顶元素但不移除 publicEpeek(){ if(top==-1){ thrownewRuntimeException("栈为空！"); }else{ return(E)data[top]; } } //弹出栈顶元素 publicEpop(){ if(top==-1){ thrownewRuntimeException("栈为空！"); }else{ return(E)data[top--]; } } //返回对象在堆栈中的位置，以1为基数 publicintsearch(Ee){ inti=top; while(top!=-1){ if(peek()!=e){ top--; }else{ break; } } intresult=top+1; top=i; returnresult; } }

栈的链式存储结构实现：

publicclassLinkStack<E>{ //链栈的节点 privateclassNode<E>{ Ee; Node<E>next; publicNode(){} publicNode(Ee,Nodenext){ this.e=e; this.next=next; } } privateNode<E>top;//栈顶元素 privateintsize;//当前栈大小 publicLinkStack(){ top=null; } //当前栈大小 publicintlength(){ returnsize; } //判空 publicbooleanempty(){ returnsize==0; } //入栈：让top指向新创建的元素，新元素的next引用指向原来的栈顶元素 publicbooleanpush(Ee){ top=newNode(e,top); size++; returntrue; } //查看栈顶元素但不删除 publicNode<E>peek(){ if(empty()){ thrownewRuntimeException("空栈异常！"); }else{ returntop; } } //出栈 publicNode<E>pop(){ if(empty()){ thrownewRuntimeException("空栈异常！"); }else{ Node<E>value=top;//得到栈顶元素 top=top.next;//让top引用指向原栈顶元素的下一个元素 value.next=null;//释放原栈顶元素的next引用 size--; returnvalue; } } }

基于LinkedList实现的栈结构：

importjava.util.LinkedList; /** *基于LinkedList实现栈 *在LinkedList实力中只选择部分基于栈实现的接口 */ publicclassStackList<E>{ privateLinkedList<E>ll=newLinkedList<E>(); //入栈 publicvoidpush(Ee){ ll.addFirst(e); } //查看栈顶元素但不移除 publicEpeek(){ returnll.getFirst(); } //出栈 publicEpop(){ returnll.removeFirst(); } //判空 publicbooleanempty(){ returnll.isEmpty(); } //打印栈元素 publicStringtoString(){ returnll.toString(); } }

队列的顺序存储结构实现

publicclassQueue<E>{ privateObject[]data=null; privateintmaxSize;//队列容量 privateintfront;//队列头，允许删除 privateintrear;//队列尾，允许插入 //构造函数 publicQueue(){ this(10); } publicQueue(intinitialSize){ if(initialSize>=0){ this.maxSize=initialSize; data=newObject[initialSize]; front=rear=0; }else{ thrownewRuntimeException("初始化大小不能小于0："+initialSize); } } //判空 publicbooleanempty(){ returnrear==front?true:false; } //插入 publicbooleanadd(Ee){ if(rear==maxSize){ thrownewRuntimeException("队列已满，无法插入新的元素！"); }else{ data[rear++]=e; returntrue; } } //返回队首元素，但不删除 publicEpeek(){ if(empty()){ thrownewRuntimeException("空队列异常！"); }else{ return(E)data[front]; } } //出队 publicEpoll(){ if(empty()){ thrownewRuntimeException("空队列异常！"); }else{ Evalue=(E)data[front];//保留队列的front端的元素的值 data[front++]=null;//释放队列的front端的元素 returnvalue; } } //队列长度 publicintlength(){ returnrear-front; } }

循环队列的顺序存储结构实现

importjava.util.Arrays; publicclassLoopQueue<E>{ publicObject[]data=null; privateintmaxSize;//队列容量 privateintrear;//队列尾，允许插入 privateintfront;//队列头，允许删除 privateintsize=0;//队列当前长度 publicLoopQueue(){ this(10); } publicLoopQueue(intinitialSize){ if(initialSize>=0){ this.maxSize=initialSize; data=newObject[initialSize]; front=rear=0; }else{ thrownewRuntimeException("初始化大小不能小于0："+initialSize); } } //判空 publicbooleanempty(){ returnsize==0; } //插入 publicbooleanadd(Ee){ if(size==maxSize){ thrownewRuntimeException("队列已满，无法插入新的元素！"); }else{ data[rear]=e; rear=(rear+1)%maxSize; size++; returntrue; } } //返回队首元素，但不删除 publicEpeek(){ if(empty()){ thrownewRuntimeException("空队列异常！"); }else{ return(E)data[front]; } } //出队 publicEpoll(){ if(empty()){ thrownewRuntimeException("空队列异常！"); }else{ Evalue=(E)data[front];//保留队列的front端的元素的值 data[front]=null;//释放队列的front端的元素 front=(front+1)%maxSize;//队首指针加1 size--; returnvalue; } } //队列长度 publicintlength(){ returnsize; } //清空循环队列 publicvoidclear(){ Arrays.fill(data,null); size=0; front=0; rear=0; } }

队列的链式存储结构实现

publicclassLinkQueue<E>{ //链栈的节点 privateclassNode<E>{ Ee; Node<E>next; publicNode(){ } publicNode(Ee,Nodenext){ this.e=e; this.next=next; } } privateNodefront;//队列头，允许删除 privateNoderear;//队列尾，允许插入 privateintsize;//队列当前长度 publicLinkQueue(){ front=null; rear=null; } //判空 publicbooleanempty(){ returnsize==0; } //插入 publicbooleanadd(Ee){ if(empty()){//如果队列为空 front=newNode(e,null);//只有一个节点，front、rear都指向该节点 rear=front; }else{ Node<E>newNode=newNode<E>(e,null); rear.next=newNode;//让尾节点的next指向新增的节点 rear=newNode;//以新节点作为新的尾节点 } size++; returntrue; } //返回队首元素，但不删除 publicNode<E>peek(){ if(empty()){ thrownewRuntimeException("空队列异常！"); }else{ returnfront; } } //出队 publicNode<E>poll(){ if(empty()){ thrownewRuntimeException("空队列异常！"); }else{ Node<E>value=front;//得到队列头元素 front=front.next;//让front引用指向原队列头元素的下一个元素 value.next=null;//释放原队列头元素的next引用 size--; returnvalue; } } //队列长度 publicintlength(){ returnsize; } }

基于LinkedList实现队列结构

/** *使用java.util.Queue接口,其底层关联到一个LinkedList（双端队列）实例. */ importjava.util.LinkedList; importjava.util.Queue; publicclassQueueList<E>{ privateQueue<E>queue=newLinkedList<E>(); //将指定的元素插入此队列（如果立即可行且不会违反容量限制），在成功时返回true， //如果当前没有可用的空间，则抛出IllegalStateException。 publicbooleanadd(Ee){ returnqueue.add(e); } //获取，但是不移除此队列的头。 publicEelement(){ returnqueue.element(); } //将指定的元素插入此队列（如果立即可行且不会违反容量限制），当使用有容量限制的队列时， //此方法通常要优于add(E)，后者可能无法插入元素，而只是抛出一个异常。 publicbooleanoffer(Ee){ returnqueue.offer(e); } //获取但不移除此队列的头；如果此队列为空，则返回null publicEpeek(){ returnqueue.peek(); } //获取并移除此队列的头，如果此队列为空，则返回null publicEpoll(){ returnqueue.poll(); } //获取并移除此队列的头 publicEremove(){ returnqueue.remove(); } //判空 publicbooleanempty(){ returnqueue.isEmpty(); } }

本文内容总结：

原文链接：https://www.cnblogs.com/CherishFX/p/4608880.html