Java栈与队列怎么实现
Java栈与队列怎么实现
本篇内容主要讲解“Java栈与队列怎么实现”，感兴趣的朋友不妨来看看。本文介绍的方法操作简单快捷，实用性强。下面就让小编来带大家学习“Java栈与队列怎么实现”吧!
1、实现循环队列
【OJ链接】
循环队列一般通过数组实现。我们需要解决几个问题。
（1）数组下标实现循环
a、下标最后再往后(offset 小于 array.length): index = (index + offset) % array.length。通俗一点，就是如果我们的数组大小为8，下标走到了7，再往后如何回到0，我们可以（index+1）%8来实现。
b、下标最前再往前的时候，我们特殊判断一下，将其置为数组大小减一即可。
（2）区分队列的满与空
我们可以给数组预留一个位置，如果rear+1=front，则表示队列已满；如果rear=front，表示队列为空。这个情况下，我们需要考虑队列大小的问题，在定义数组大小时，需要比原有的大一。
【代码如下】
classMyCircularQueue{publicintfront;publicintrear;publicint[]array;//构造方法publicMyCircularQueue(intk){//因为预留位置的缘故，数组的大小要定义为k+1this.array=newint[k+1];}//入队publicbooleanenQueue(intvalue){if(isFull()){returnfalse;}this.array[this.rear]=value;this.rear=(this.rear+1)%this.array.length;returntrue;}//出队publicbooleandeQueue(){if(isEmpty()){returnfalse;}this.front=(this.front+1)%this.array.length;returntrue;}//获取队头publicintFront(){if(isEmpty()){return-1;}returnthis.array[front];}//获取队尾publicintRear(){if(isEmpty()){return-1;}intindex=-1;if(this.rear==0){index=this.array.length-1;}else{index=this.rear-1;}returnthis.array[index];}//判断是否为空publicbooleanisEmpty(){if(this.front==this.rear){returntrue;}returnfalse;}//判断队列是否满publicbooleanisFull(){if((this.rear+1)%this.array.length==this.front){returntrue;}returnfalse;}}
2、队列实现栈
【OJ链接】
因为栈的先进后出、队列的先进先出原则。我们需要两个队列来实现栈。当两个队列都为空时，栈为空。
入栈（push）：第一次入栈无所谓，两个队列都为空，随便选择一个队列入队即可；后面入栈时，肯定会有一个队列不为空，找到不为空的队列，进行入队操作。
出栈（pop）：首先栈为空时，不能进行出栈操作；栈不为空时，肯定有一个队列为空（queue1），一个队列不为空（queue2），将queue1中的size-1个元素出栈到queue2中（特别注意不能将求queue1大小的函数放进循环里，queue进行出队操作时，其大小是改变的），最后将queue1中最后一个元素进行出队最为返回值。
获取栈顶元素（top）：和出栈差不多，就不细说了
【代码如下】
classMyStack{privateQueue<Integer>queue1;privateQueue<Integer>queue2;//构造方法publicMyStack(){queue1=newLinkedList<>();queue2=newLinkedList<>();}//入栈publicvoidpush(intx){if(!queue2.isEmpty()){queue2.offer(x);}else{queue1.offer(x);}}//出栈publicintpop(){if(empty()){return-1;}if(queue1.isEmpty()){intsize=queue2.size();for(inti=0;i<size-1;++i){intx=queue2.poll();queue1.offer(x);}returnqueue2.poll();}else{intsize=queue1.size();for(inti=0;i<size-1;++i){intx=queue1.poll();queue2.offer(x);}returnqueue1.poll();}}//获取栈顶元素publicinttop(){if(empty()){return-1;}if(queue1.isEmpty()){intx=-1;intsize=queue2.size();for(inti=0;i<size;++i){x=queue2.poll();queue1.offer(x);}returnx;}else{intsize=queue1.size();intx=-1;for(inti=0;i<size;++i){x=queue1.poll();queue2.offer(x);}returnx;}}//判断栈是否为空publicbooleanempty(){if(queue1.isEmpty()&&queue2.isEmpty()){returntrue;}returnfalse;}}
3、栈实现队列
【OJ链接】
还是和上面一样，需要用到两个栈（stack1、stack2）。和实现栈列不同的是，入队只能对同一个栈进行操作。如果两个栈都为空，则队列为空。
入队（push）：规定stack1用来入队。每次入队时，对stack1进行入栈操作即可。
出队（pop）：规定stack2进行出队操作。如果队列为空时，不能进行出队操作。当stack2为空时，我们需要将stack1中所有元素出栈，放入stack2中，然后对stack2进行出栈操作。如果stack2不为空，则直接对stack2进行出栈操作即可。
获取队列开头元素（peek）：和出栈操作相同，最后只需要获取stack2的栈顶元素即可。
【代码如下】
classMyQueue{privateStack<Integer>stack1;privateStack<Integer>stack2;//构造方法publicMyQueue(){stack1=newStack<>();stack2=newStack<>();}//入队操作publicvoidpush(intx){stack1.push(x);}//出队操作publicintpop(){if(stack2.empty()){intsize=stack1.size();for(inti=0;i<size;++i){intx=stack1.pop();stack2.push(x);}}returnstack2.pop();}//获取队列开头的元素publicintpeek(){if(stack2.empty()){intsize=stack1.size();for(inti=0;i<size;++i){intx=stack1.pop();stack2.push(x);}}returnstack2.peek();}//判断队列是否为空publicbooleanempty(){if(stack1.empty()&&stack2.empty()){returntrue;}returnfalse;}}
4、实现最小栈
【OJ链接】
其实就是要在O(1)的时间复杂度内找到栈的最小元素。需要两个栈来实现，一个栈来进行出栈、入栈操作。只需要保证不管如何操作，另一个栈的栈顶元素都是当前栈的最小元素即可。
两个栈stack1、stack2，站的操作都在stack1中：
入栈：如果第一次入栈，我们需要将其也放入stack2中，之后的入栈，将入栈元素与stack2的栈顶元素进行比较，如果其小于stack2的栈顶元素，则将其放入stack2中。
出栈：对stack1出栈时，将其与stack2的栈顶元素进行比较，如果其等于stack2的栈顶元素，则对stack2进行出栈操作。
这样就能保证stack2的栈顶元素总是stack1的最小元素。注意：如果stack1中入栈两个相同的最小元素，都需要对stack2进行入栈。
【代码如下】
classMinStack{privateStack<Integer>stack1;privateStack<Integer>stack2;//构造方法publicMinStack(){stack1=newStack<>();stack2=newStack<>();}//入栈publicvoidpush(intval){stack1.push(val);if(stack2.empty()){stack2.push(val);}else{if(val<=stack2.peek()){stack2.push(val);}}}//出栈publicvoidpop(){intx=stack1.pop();if(x==stack2.peek()){stack2.pop();}}//获取栈顶元素publicinttop(){returnstack1.peek();}//获取栈的最小元素publicintgetMin(){returnstack2.peek();}}
到此，相信大家对“Java栈与队列怎么实现”有了更深的了解，不妨来实际操作一番吧！这里是恰卡编程网网站，更多相关内容可以进入相关频道进行查询，关注我们，继续学习！
