优先队列与递归

前言

如果按照队列的特点，即先来先服务原则，在很多情况下不能实现相关设计，比如操作系统中的进程调度管理，就是按照优先级大小来进行调度

优先队列

若一个队列中的每个元素都有一个优先级，每次出队的是具有优先级最高的元素，则称该队列为优先队列

public class PriorityQueue<T extends Comparable<T>> implements QQueue{

	private SortedSinglyLinkedList<T> list; //使用排序单链表存储队列元素
	
	public PriorityQueue(){   //构造空队列
		this.list=new SortedSinglyLinkedList<T>();
	}
	
	public boolean isEmpty() { //判断队列是否为空
		return list.isEmpty();
	}

	public void enqueue(Object x) { //元素x入队，根据元素大小插入在单链表适当位置
		list.insert(x);
		
	}

	public Object dequeue() {//出队，返回对头元素

		return list.remove(0);
	}

	public String toString(){
		return list.toString();
	}
}

进程按优先级调度管理

public class Process implements Comparable<Process>{

	private String name;   //进程名
	private int priority;  //优先级


	public Process(String name, int priority) {
		super();
		this.name = name;
		this.priority = priority;
	}
	
	
	public int compareTo(Process o) {//比较两个进程的大小，约定进程排队次序的规则

		return this.priority-o.priority;
	}

}

递归

从形式上，递归的定义可如下所示

同时递归定义必须满足以下两个条件
1.边界条件：至少有一条初始定义是非递归的。
2.递归通式： 由已知函数值逐步递推计算出未知函数值

递归算法是指直接或者间接调用自身的算法
如用递归算法求fibonacci数列

public class Factorial {

	public static int factorial(int n)
	{
		if(n<0)
			throw new IllegalArgumentException("n="+n);
		if(n==0||n==1)
			return n;
		return factorial(n-1)+factorial(n-2);
	}
	
	public static void main(String args[]){
		for(int i=0;i<=24;i++)
			System.out.print(factorial(i)+" ");
		
	}
}

运行结果：

0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765 10946 17711 28657 46368

再如将之前的SinglyLinkenList类增加一个复制方法，采用递归法

private Node<T> copy(Node<T> p){
	Node<T> q=null; //新结点
	if(p!=null)  //要复制的结点非空
	{
		q=new Node<T>(p.data,null); //相当于q.data=p.data，q.next=null
		q.next=copy(p.next);//递归，q1.data=p.next.data，q1.next=null，先返回q1，q.next=q1
		//可以看成一棵二叉树
	}
	return q;
}