栈和队列的相互转化

 先看队列转化成栈的操作:

首先需要准备两个队列,一个用来装数据(data),另一个用来辅助(help)。

假设把以串数据进入到队列data中,例如:[1,2,3,4,5,6]  右边是第一个数。

需要实现栈必定是后进先出。那么需要辅助队列,把[2,3,4,5,6]放入到help辅助队列中。

然后把data队列中的[1]返回,在把队列help赋值给data队列完成一次出栈操作。

代码:

package com.栈队组;

import java.util.LinkedList;
import java.util.Queue;

public class Queue_To_Stack {
	private static Queue<Integer> data ;  //原本的数据队列
	private static Queue<Integer> help ; 	// 辅助队列
	
	public static void setStack(){  //定义一个栈
		data = new LinkedList<>();
		help = new LinkedList<>();
	}
	public static void push(int num){   //压入栈
		data.add(num);    
	}
	public static Integer pop(){    //出栈
		if(data.isEmpty()){
			throw new IllegalArgumentException("栈为空!") ;
		}
		while(data.size() > 1){   //全部出队列,直到最后一个
			help.add(data.poll()) ;
		}
		int res = data.poll();  //得到最后一个
		swpe();  // help  和   data交换
		return res ;
	}
	
	public static Integer peek(){   //栈顶元素
		if(data.isEmpty()){
			throw new IllegalArgumentException("栈为空!") ;
		}
		while(data.size() > 1){
			help.add(data.poll()) ;
		}
		int res = data.poll();
		data.add(res) ;
		swpe();
		return res ;
	}
	
	public static void swpe(){
		Queue<Integer> tmp = help;
		help = data;
		data = tmp;
  	}
	public static void main(String[] args) {
		setStack();
		push(2);
		push(44);
		push(11);
		push(266);
		push(277);
		push(200);
		System.out.println(pop());
		System.out.println(peek());
	}

}

再看栈转队列

首先准备两个栈,一个数据栈,一个辅助栈。

假设栈中有[1,2,3,4,5,6] 右边是栈顶。队列是先进先出的。所以需要把1先拿出来。这时我们就利用help辅助栈把[1,2,3,4,5,6]压入到hlep中,从help栈顶取出[1],再把[2,3,4,5,6]压入data.完成一次出栈操作。

package com.栈队组;

import java.util.Stack;

public class Stack_To_Queue {
	private static  Stack<Integer> data;
	private static Stack<Integer> help ;
	
	public static void setQueue(){
		data = new Stack<>();
		help = new Stack<>();
	}
	public static void add(int num){
		data.push(num) ;
	}
	public static Integer poll(){
		if(data.isEmpty() && help.isEmpty()){
			throw new RuntimeException("队列为空!") ;
		}else{
			while(data.size()>0){
				help.push(data.pop()) ;
			}
			int res = help.pop();
			while(!help.isEmpty()){
				data.push(help.pop()) ;
			}
			return res ;
		}
	}
	public static Integer peek(){
		if(data.isEmpty() && help.isEmpty()){
			throw new RuntimeException("队列为空!") ;
		}else{
			while(data.size()>0){
				help.push(data.pop()) ;
			}
			int res = help.peek();
			while(!help.isEmpty()){
				data.push(help.pop()) ;
			}
			return res ;
		}
	}
	public static void main(String[] args) {
		setQueue();
		add(1);
		add(2);
		add(3);
		add(4);
		add(5);
		help.push(7);
		help.push(7);
		help.push(7);
		help.push(7);
		System.out.println(poll());
		System.out.println(poll());
		System.out.println(poll());
		System.out.println(poll());
		System.out.println(poll());
		System.out.println(poll());
		System.out.println(poll());
		System.out.println(poll());
		System.out.println(poll());
	}
}

 

全部评论

相关推荐

评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客企业服务