Java数据结构之 链式队列、优先级队列

一. 链式队列

队列的特点是先进先出，之前已经用顺序结构实现了队列，现在我们考虑用链表来实现队列的一系列操作。

入队用头插法：如果入队用头插法（复杂度O（1）），出队就需要遍历整个单链表（O（n））

入队用尾插法：如果入队用尾插法（复杂度O（n））,出队只需要删除头结点后的节点（O（1））

现在考虑如何让入队出队的时间复杂度都为O（1）呢？

可以在头结点设两个指针域，一个指向队头，一个指向队尾。在队头删除，队尾插入（尾插法）即可。

1. 初始化链式队列

class QueueLink2{
	
	
	class Entry{
		int data;//数据域
		Entry next;//指针域
		
		public Entry(){
			this.data = -1;
			this.next = null;
		}
		public Entry(int val){//带参构造函数
			this.data = val;
			this.next = null;
		}
	}
	private Entry front = null;//队头
	private Entry rear = null;//队尾
	private int usedSize = 0;//队列的有效元素个数
}

2.判断队空

public boolean isEmpty(){
		return this.usedSize == 0;
	}

3.入队

public void insertTail(int val){
		Entry entry = new Entry(val);
		if(isEmpty()){//队列为空，先让front和rear都指向entry
			front = entry;
			rear = entry;
		}else{//插入，队头不变，在队尾插入
			rear.next = entry;
			rear = entry;
		}
		this.usedSize++;//队列长度自增
	}

4.出队

public void pop(){
		if(isEmpty()){
			return;
		}else{
			Entry cur = this.front;
			this.front = cur.next;
			cur = null;//将出队的元素置为空
			this.usedSize--;//队列长度减一
		}
	}

5.得到队头

public int getTop(){
		if(isEmpty()){
			return -1;
		}
		return front.data;
	}

二. 优先级队列

按优先级大小进行插入，优先级高的在前面，优先级低的在后面

1. 初始化

class PrioLink{
	
	private Entry head = null;
	class Entry{
		int data;//数据域
		Entry next;
		int prio;//优先级
		
		public Entry(){//头节点的构造函数
			this.data = -1;
			this.prio = -1;
			this.next = null;
		}
		public Entry(int val,int prio){
			this.data = val;
			this.prio = prio;
			this.next = null;
		}
	}
	public PrioLink(){
		this.head = new Entry();
	}
}

2. 插入

public void insert(int val,int prio){
		Entry entry = new Entry(val,prio);
		Entry cur = head;
		while(cur.next != null){
			if(cur.next.prio > entry.prio){//找第一个比当前要插入节点优先级低的元素，即找到了要插入的位置
				break;
			}
			cur = cur.next;
		}
		//插入节点
		entry.next = cur.next;
		cur.next = entry;
	}

3.删除

public void pop(){
		Entry cur = this.head.next;
		if(cur == null){
			return;
		}
		head.next = cur.next;
		cur = null;
	}

4.得到优先级最高的节点

public int getTop(){
		return head.next.data;
	}