【Java数据结构】队列

队列

先进先出的线性表，它只允许在一端(队尾)进行插入操作，在另一端（队首）进行删除操作。与栈的插入和删除都在栈顶进行不同。

1.普通队列

实例代码:

存储类型为long的队列

package cn.deu;

public class Queue {
   //队列组合
   private long [] arr;
   //数组最大值
   private int MaxSize=0;
   //数组有效值
   private int num=0;
   //队头
   private int font=0;
   //队尾
   private int end=0;  
   
   public Queue(int n) {
	   this.MaxSize=n;
      arr=new long[n];
      num=0;
      font=0;
      end=-1;
   }
   
   //插入数据
   public void insert(long n){
	   arr[++end]=n;
	   num++;
   }
   
   //删除数据
   public long remove(){
	   num--;
	   return arr[font++];
   }
   
   //是否为空
   public boolean isEmpty(){
	   return (num==0);
   }
   
   //是否为满
   public boolean isFull(){
	   return (end==MaxSize-1);
   }
   
   //返回有效元素大小
   public long size(){
	   return num;
   }
   
   //刷新队列
   public void NewQueue(){
	   end=-1;
	   font=0;
   }
   
}

package en.edu.Test;

import cn.deu.Queue;

public class TestQueue {


	public static void main(String[] args) {
		Queue queue=new Queue(5);
		
		System.out.println(queue.isEmpty());
		
		queue.insert(50);
		queue.insert(20);
		queue.insert(10);
		queue.insert(2);
		queue.insert(1);
		
		System.out.println(queue.isEmpty());
		System.out.println(queue.isFull());
		
		while(!queue.isEmpty()){
			System.out.println(queue.remove());
		}
		
		if(queue.isFull()){
			queue.NewQueue();
		}
		
		queue.insert(20);
		System.out.println(queue.remove());
	}
}

true
false
true
50
20
10
2
1
20

2.优先级队列
核心思想：在优先级队列，数据项案关键字的值有序，这样关键字最小的数据项(捉着最大)总是在队头，数据项插入时会按照顺序插入到合适的位置。

模型：

package cn.deu;

public class PriorityQueue {
	   //队列组合
	   private long [] arr;
	   //数组最大值
	   private int MaxSize=0;
	   //数组有效值
	   private int num=0;
	   //队头就是数组的第一个，队尾就是数组的最后一个
	   
	   public PriorityQueue(int n) {
		   this.MaxSize=n;
	      arr=new long[n];
	      num=0;
	   }
	   
	   //插入数据
	   public void insert(long n){
		   //找到第一个小于n的，将n差到它后面
		   int i;
		   for(i=0;i<num;i++){
			   if(n>arr[i]){
				   break;
			   }
		   }
		   
		   for(int j=num;j>i;j--){
			   arr[j]=arr[j-1];
		   }
		   arr[i]=n;
		   num++;
	   }
	   
	   //删除数据
	   public long remove(){
		   //直接移除最后一项
		   long value=arr[num-1];
		   num--;
		   return value;
	   }
	   
	   //是否为空
	   public boolean isEmpty(){
		   return (num==0);
	   }
	   
	   //是否为满
	   public boolean isFull(){
		   return (num==MaxSize);
	   }
	   
	   //返回有效元素大小
	   public long size(){
		   return num;
	   }
	   
	   //刷新队列
	   public void NewQueue(){
		  num=0;
	   }
	   
	  //输出队头
	   public long getFont(){
		   return arr[0];
	   }
	   
	 //输出队尾
	   public long getEnd(){
		   return arr[num-1];
	   }
}

package en.edu.Test;

import cn.deu.PriorityQueue;

public class TeatQ {
		public static void main(String[] args) {
			PriorityQueue pq=new PriorityQueue(10);
			pq.insert(30);
			pq.insert(45);
			pq.insert(15);
			pq.insert(2);
			pq.insert(1);
			
			System.out.println("队头元素为"+pq.getFont());
			System.out.println("队尾元素为"+pq.getEnd());
			while(!pq.isEmpty()){
				long value=pq.remove();
				//从队尾向前输出
				System.out.print(value+" ");
			}
			System.out.println();
			
			pq.insert(3);
			pq.insert(2);
			pq.insert(1);
			
			System.out.println("队头元素为"+pq.getFont());
			System.out.println("队尾元素为"+pq.getEnd());
			
			pq.insert(0);
			
			System.out.println("队头元素为"+pq.getFont());
			System.out.println("队尾元素为"+pq.getEnd());
			
			pq.insert(4);
			
			System.out.println("队头元素为"+pq.getFont());
			System.out.println("队尾元素为"+pq.getEnd());
				
		}
}