两个栈实现一个队列

╰+哭是因爲堅強的太久メ 2022-05-26 06:15 221阅读 0赞

<table> 
 <tbody> 
 <tr> 
 <td>package&nbsp;栈;&nbsp;/**两个栈实现一个队列&nbsp;* &nbsp;* 思路：&nbsp;* 栈1用于存储元素，栈2用于弹出元素。负负得正。&nbsp;* 每次添加都往栈1中添加；&nbsp;* 每次弹出都从栈2弹出；&nbsp;* &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;如果栈2不为空，直接弹出栈2中的元素；&nbsp;* &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;如果栈2为空，这时要判断栈1是否为空&nbsp;* &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;若栈1为空，返回错误，&nbsp;* &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;若栈1不为空，则将栈1中的元素全部弹到栈2，然后从栈2中弹出元素。&nbsp;*/public&nbsp;class&nbsp;Queue { 
 <blockquote style="margin:0 0 0 40px;border:none;padding:0px;"> 
 Stack stack1&nbsp;= new&nbsp;Stack(); 
 Stack stack2&nbsp;= new&nbsp;Stack(); 
 
 /** 
 &nbsp;* 每次添加都往栈1里面添加 
 &nbsp;* @param&nbsp;data 
 &nbsp;*/ 
 public&nbsp;void&nbsp;push(Integer data){ 
 </blockquote> 
 <blockquote style="margin:0 0 0 40px;border:none;padding:0px;"> 
 <blockquote style="margin:0 0 0 40px;border:none;padding:0px;"> 
 stack1.push(data); 
 </blockquote> 
 </blockquote> 
 <blockquote style="margin:0 0 0 40px;border:none;padding:0px;"> 
 } 
 
 /** 
 &nbsp;* 每次弹出都从栈2弹出； 
 &nbsp;* &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;如果栈2不为空，直接弹出栈2中的元素； 
 &nbsp;* &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;如果栈2为空，这时要判断栈1是否为空 
 &nbsp;* &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;若栈1为空，返回错误， 
 &nbsp;* &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;若栈1不为空，则将栈1中的元素全部弹到栈2，然后从栈2中弹出元素。 
 &nbsp;* @return 
 &nbsp;*/ 
 public&nbsp;Integer pop(){ 
 </blockquote> 
 <blockquote style="margin:0 0 0 40px;border:none;padding:0px;"> 
 <blockquote style="margin:0 0 0 40px;border:none;padding:0px;"> 
 if(stack2.isEmpty()){ 
 </blockquote> 
 </blockquote> 
 <blockquote style="margin:0 0 0 40px;border:none;padding:0px;"> 
 <blockquote style="margin:0 0 0 40px;border:none;padding:0px;"> 
 <blockquote style="margin:0 0 0 40px;border:none;padding:0px;"> 
 if(stack1.isEmpty()){ 
 </blockquote> 
 </blockquote> 
 </blockquote> 
 <blockquote style="margin:0 0 0 40px;border:none;padding:0px;"> 
 <blockquote style="margin:0 0 0 40px;border:none;padding:0px;"> 
 <blockquote style="margin:0 0 0 40px;border:none;padding:0px;"> 
 <blockquote style="margin:0 0 0 40px;border:none;padding:0px;"> 
 return&nbsp;-1; 
 </blockquote> 
 </blockquote> 
 </blockquote> 
 </blockquote> 
 <blockquote style="margin:0 0 0 40px;border:none;padding:0px;"> 
 <blockquote style="margin:0 0 0 40px;border:none;padding:0px;"> 
 <blockquote style="margin:0 0 0 40px;border:none;padding:0px;"> 
 }else{ 
 </blockquote> 
 </blockquote> 
 </blockquote> 
 <blockquote style="margin:0 0 0 40px;border:none;padding:0px;"> 
 <blockquote style="margin:0 0 0 40px;border:none;padding:0px;"> 
 <blockquote style="margin:0 0 0 40px;border:none;padding:0px;"> 
 <blockquote style="margin:0 0 0 40px;border:none;padding:0px;"> 
 while(!stack1.isEmpty()){ 
 </blockquote> 
 </blockquote> 
 </blockquote> 
 </blockquote> 
 <blockquote style="margin:0 0 0 40px;border:none;padding:0px;"> 
 <blockquote style="margin:0 0 0 40px;border:none;padding:0px;"> 
 <blockquote style="margin:0 0 0 40px;border:none;padding:0px;"> 
 <blockquote style="margin:0 0 0 40px;border:none;padding:0px;"> 
 <blockquote style="margin:0 0 0 40px;border:none;padding:0px;"> 
 stack2.push(stack1.pop()); 
 </blockquote> 
 </blockquote> 
 </blockquote> 
 </blockquote> 
 </blockquote> 
 <blockquote style="margin:0 0 0 40px;border:none;padding:0px;"> 
 <blockquote style="margin:0 0 0 40px;border:none;padding:0px;"> 
 <blockquote style="margin:0 0 0 40px;border:none;padding:0px;"> 
 <blockquote style="margin:0 0 0 40px;border:none;padding:0px;"> 
 } 
 </blockquote> 
 </blockquote> 
 </blockquote> 
 </blockquote> 
 <blockquote style="margin:0 0 0 40px;border:none;padding:0px;"> 
 <blockquote style="margin:0 0 0 40px;border:none;padding:0px;"> 
 <blockquote style="margin:0 0 0 40px;border:none;padding:0px;"> 
 } 
 </blockquote> 
 </blockquote> 
 </blockquote> 
 <blockquote style="margin:0 0 0 40px;border:none;padding:0px;"> 
 <blockquote style="margin:0 0 0 40px;border:none;padding:0px;"> 
 } 
 </blockquote> 
 <blockquote style="margin:0 0 0 40px;border:none;padding:0px;"> 
 return&nbsp;stack2.pop(); 
 </blockquote> 
 </blockquote> 
 <blockquote style="margin:0 0 0 40px;border:none;padding:0px;"> 
 } 
 
 /** 
 &nbsp;* 取队列的峰值 
 &nbsp;* @return 
 &nbsp;*/ 
 public&nbsp;Integer peek(){ 
 </blockquote> 
 <blockquote style="margin:0 0 0 40px;border:none;padding:0px;"> 
 <blockquote style="margin:0 0 0 40px;border:none;padding:0px;"> 
 if(stack2.isEmpty()){ 
 </blockquote> 
 </blockquote> 
 <blockquote style="margin:0 0 0 40px;border:none;padding:0px;"> 
 <blockquote style="margin:0 0 0 40px;border:none;padding:0px;"> 
 <blockquote style="margin:0 0 0 40px;border:none;padding:0px;"> 
 if(stack1.isEmpty()){ 
 </blockquote> 
 </blockquote> 
 </blockquote> 
 <blockquote style="margin:0 0 0 40px;border:none;padding:0px;"> 
 <blockquote style="margin:0 0 0 40px;border:none;padding:0px;"> 
 <blockquote style="margin:0 0 0 40px;border:none;padding:0px;"> 
 <blockquote style="margin:0 0 0 40px;border:none;padding:0px;"> 
 return&nbsp;-1; 
 </blockquote> 
 </blockquote> 
 </blockquote> 
 </blockquote> 
 <blockquote style="margin:0 0 0 40px;border:none;padding:0px;"> 
 <blockquote style="margin:0 0 0 40px;border:none;padding:0px;"> 
 <blockquote style="margin:0 0 0 40px;border:none;padding:0px;"> 
 }else{ 
 </blockquote> 
 </blockquote> 
 </blockquote> 
 <blockquote style="margin:0 0 0 40px;border:none;padding:0px;"> 
 <blockquote style="margin:0 0 0 40px;border:none;padding:0px;"> 
 <blockquote style="margin:0 0 0 40px;border:none;padding:0px;"> 
 <blockquote style="margin:0 0 0 40px;border:none;padding:0px;"> 
 while(!stack1.isEmpty()){ 
 </blockquote> 
 </blockquote> 
 </blockquote> 
 </blockquote> 
 <blockquote style="margin:0 0 0 40px;border:none;padding:0px;"> 
 <blockquote style="margin:0 0 0 40px;border:none;padding:0px;"> 
 <blockquote style="margin:0 0 0 40px;border:none;padding:0px;"> 
 <blockquote style="margin:0 0 0 40px;border:none;padding:0px;"> 
 <blockquote style="margin:0 0 0 40px;border:none;padding:0px;"> 
 stack2.push(stack1.pop()); 
 </blockquote> 
 </blockquote> 
 </blockquote> 
 </blockquote> 
 </blockquote> 
 <blockquote style="margin:0 0 0 40px;border:none;padding:0px;"> 
 <blockquote style="margin:0 0 0 40px;border:none;padding:0px;"> 
 <blockquote style="margin:0 0 0 40px;border:none;padding:0px;"> 
 <blockquote style="margin:0 0 0 40px;border:none;padding:0px;"> 
 } 
 </blockquote> 
 </blockquote> 
 </blockquote> 
 </blockquote> 
 <blockquote style="margin:0 0 0 40px;border:none;padding:0px;"> 
 <blockquote style="margin:0 0 0 40px;border:none;padding:0px;"> 
 <blockquote style="margin:0 0 0 40px;border:none;padding:0px;"> 
 } 
 </blockquote> 
 </blockquote> 
 </blockquote> 
 <blockquote style="margin:0 0 0 40px;border:none;padding:0px;"> 
 <blockquote style="margin:0 0 0 40px;border:none;padding:0px;"> 
 } 
 </blockquote> 
 </blockquote> 
 <blockquote style="margin:0 0 0 40px;border:none;padding:0px;"> 
 <blockquote style="margin:0 0 0 40px;border:none;padding:0px;"> 
 return&nbsp;stack2.peek(); 
 </blockquote> 
 </blockquote> 
 <blockquote style="margin:0 0 0 40px;border:none;padding:0px;"> 
 } 
 
 /** 
 &nbsp;* 判断队列是否为空 
 &nbsp;* @return 
 &nbsp;*/ 
 public&nbsp;boolean&nbsp;isEmpty(){ 
 </blockquote> 
 <blockquote style="margin:0 0 0 40px;border:none;padding:0px;"> 
 <blockquote style="margin:0 0 0 40px;border:none;padding:0px;"> 
 return&nbsp;stack1.isEmpty() &amp;&amp; stack2.isEmpty(); 
 </blockquote> 
 </blockquote> 
 <blockquote style="margin:0 0 0 40px;border:none;padding:0px;"> 
 } 
 
 /** 
 &nbsp;* 主函数 
 &nbsp;* @param&nbsp;args 
 &nbsp;*/ 
 public&nbsp;static&nbsp;void&nbsp;main(String[] args) { 
 </blockquote> 
 <blockquote style="margin:0 0 0 40px;border:none;padding:0px;"> 
 <blockquote style="margin:0 0 0 40px;border:none;padding:0px;"> 
 Queue queue&nbsp;= new&nbsp;Queue(); 
 </blockquote> 
 <blockquote style="margin:0 0 0 40px;border:none;padding:0px;"> 
 queue.push(1); 
 </blockquote> 
 <blockquote style="margin:0 0 0 40px;border:none;padding:0px;"> 
 queue.push(2); 
 </blockquote> 
 <blockquote style="margin:0 0 0 40px;border:none;padding:0px;"> 
 queue.push(3); 
 </blockquote> 
 <blockquote style="margin:0 0 0 40px;border:none;padding:0px;"> 
 queue.push(4); 
 </blockquote> 
 <blockquote style="margin:0 0 0 40px;border:none;padding:0px;"> 
 
 </blockquote> 
 <blockquote style="margin:0 0 0 40px;border:none;padding:0px;"> 
 while(!queue.isEmpty()){ 
 </blockquote> 
 </blockquote> 
 <blockquote style="margin:0 0 0 40px;border:none;padding:0px;"> 
 <blockquote style="margin:0 0 0 40px;border:none;padding:0px;"> 
 <blockquote style="margin:0 0 0 40px;border:none;padding:0px;"> 
 System.out.println(queue.pop()); 
 </blockquote> 
 </blockquote> 
 </blockquote> 
 <blockquote style="margin:0 0 0 40px;border:none;padding:0px;"> 
 <blockquote style="margin:0 0 0 40px;border:none;padding:0px;"> 
 } 
 </blockquote> 
 </blockquote> 
 <blockquote style="margin:0 0 0 40px;border:none;padding:0px;"> 
 } 
 </blockquote>}</td> 
 </tr> 
 </tbody> 
</table>