Java数据结构之队列

叁歲伎倆 2022-01-31 00:21 255阅读 0赞

# 基本概念 #

队列是一种特殊的线性表，其插入操作只能在表的尾部进行，叫入队，这一端被称为队尾，删除操作只能在表的头部进行，叫出队，这一端被称为队首。没有数据元素的队列称为空队列。队列具有FIFO（先进先出）的特点，队列的底层数据结构可以用数组来实现。

# 队列的抽象数据类型 #

package ch03;
    
    public interface IQueue {
    	public void clear();
    	public boolean isEmpty();
    	public int length();
    	public Object peek();
    	public void offer(Object x) throws Exception;
    	public Object poll();
    	public void display();
    }

# 顺序队列 #

定义两个指针域头指针front和尾指针rear，front指向队列的队首元素位置，rear指向队尾元素的下一个存储单元，根据入队和出队操作实时的改变两个指针的位置即可，如图1所示。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDI3MDI0OA_size_16_color_FFFFFF_t_70]

### 代码实现 ###

package ch03;
    
    /*顺序队列*/
    public class SqQueue implements IQueue {
    	private Object[] queueItem;	//存储队列中的元素
    	private int front;	//指向队首元素
    	private int rear;	//指向队尾元素的下一个存储单元
    	private int maxSize;//最大存储个数
    	
    	public SqQueue(int maxSize) {
    		queueItem = new Object[maxSize];
    		this.maxSize = maxSize;
    		front=rear=0;
    	}
    
    	//清空顺序队列
    	public void clear() {
    		front=rear=0;
    	}
    
    	//是否为空队列
    	public boolean isEmpty() {
    		return front==rear;
    	}
    
    	//获取队列长度
    	public int length() {
    		return rear-front;
    	}
    
    	//获取队首元素
    	public Object peek() {
    		if(isEmpty())
    			return null;
    		else
    			return queueItem[front];
    	}
    
    	//入队
    	public void offer(Object x) throws Exception {
    		if(rear==maxSize)
    			throw new Exception("队列已满！");
    		queueItem[rear] = x;
    		rear++;
    	}
    
    	//出队
    	public Object poll() {
    		if(isEmpty())
    			return null;
    		front++;
    		return queueItem[front-1];
    	}
    
    	@Override
    	public void display() {
    		// TODO Auto-generated method stub
    
    	}
    }

# 循环队列 #

在顺序队列出队后，会产生空白的存储空间，由于头指针和尾指针只能顺序向后移动，故会造成有存储空间却不能进行入队操作的“假溢出”现象，如图2所示。  
![在这里插入图片描述][20190515092624251.PNG]  
为了解决顺序队列因数组下标越界而引起的“溢出”问题，可将顺序队列的首尾相连，形成循环队列。在形成循环队列后，会发现队空和队满的判定条件都变为了front=rear，如图3所示。为了解决这一问题，可以少利用一个存储单元，队列最多存放maxSize-1个数据元素，队空的判定条件为front=rear，队满的判定条件为front=(rear+1)%maxSize。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDI3MDI0OA_size_16_color_FFFFFF_t_70 1]

### 代码实现 ###

package ch03;
    
    public class CircleQueue implements IQueue{
    	private Object[] queueItem;
    	private int front;	//指向队首元素
    	private int rear;	//指向队尾元素的下一个存储单元
    	private int maxSize;//最大存储个数
    	
    	public CircleQueue(int maxSize) {
    		queueItem = new Object[maxSize];
    		this.maxSize = maxSize;
    		front=rear=0;
    	}
    
    	//清空顺序队列
    	public void clear() {
    		front=rear=0;
    	}
    
    	//是否为空队列
    	public boolean isEmpty() {
    		return front==rear;
    	}
    
    	//获取队列长度
    	public int length() {
    		return rear-front;
    	}
    
    	//获取队首元素
    	public Object peek() {
    		if(isEmpty())
    			return null;
    		else
    			return queueItem[front];
    	}
    
    	//入队
    	public void offer(Object x) throws Exception {
    		if((rear+1)%maxSize==front)
    			throw new Exception("队列已满！");
    		queueItem[rear] = x;
    		rear=(rear+1)%maxSize;
    	}
    
    	//出队
    	public Object poll() {
    		if(isEmpty())
    			return null;
    		front=(front+1)%maxSize;
    		return queueItem[front-1];
    	}
    
    	@Override
    	public void display() {
    		// TODO Auto-generated method stub
    
    	}
    }

# 链队列 #

链队列采用单链表结构，由于入队和出队分别在队尾和队首进行，不存在在队列的任意位置进行插入和删除的情况，故无需设置头结点，只需将指针front和rear分别指向队首结点和队尾结点，每个结点的指针域指向其后继结点即可。

### 代码实现 ###

package ch03;
    import ch02.Node;
    
    public class LinkQueue implements IQueue {
    	private Node front;	//头指针
    	private Node rear;	//尾指针
    	
    	public LinkQueue() {
    		front=rear=null;
    	}
    
    	//清空队列
    	public void clear() {
    		// TODO Auto-generated method stub
    		front=rear=null;
    	}
    
    	//判断是否为空队列
    	public boolean isEmpty() {
    		// TODO Auto-generated method stub
    		return front==null;
    	}
    
    	//获取队列的长度
    	public int length() {
    		// TODO Auto-generated method stub
    		Node p = front;
    		int length=0;
    		while(p!=null) {
    			p = p.next;
    			length++;
    		}
    		return length;
    	}
    
    	//获取队列的头元素
    	public Object peek() {
    		// TODO Auto-generated method stub
    		if(this.isEmpty())
    			return null;
    		return front.data;
    	}
    
    	//入列
    	public void offer(Object x) throws Exception {
    		// TODO Auto-generated method stub
    		Node newNode = new Node(x);
    		if(!isEmpty()) {
    			rear.next=newNode;
    			rear=newNode;
    		}else {
    			front=rear=newNode;
    		}
    		
    	}
    
    	//出列
    	public Object poll() {
    		// TODO Auto-generated method stub
    		if(isEmpty())
    			return null;
    		Node p = front;
    		front = front.next;
    		if(p==rear)
    			rear=null;
    		return p.data;
    	}
    
    	@Override
    	public void display() {
    		// TODO Auto-generated method stub
    
    	}
    }

# 优先级队列 #

在某些排队等待的实际问题中，有时按照“先来先服务”的原则不能满足需求，还需要按照任务的重要程度进行排列，因此，引入优先级队列。  
优先级队列是在普通队列的基础之上将队列中的数据元素按照关键字值进行排列。其删除操作仍旧是在队首进行，但插入操作不一定在队尾进行，而是按照优先级插入到队列的合适位置。由于优先级队列需要频繁的进行插入操作，而顺序队列的结构需要移动大量的元素，时间复杂度较高，因此，往往采用链队列的结构来实现。

### 优先级队列结点类 ###

package ch03;
    import ch02.Node;
    
    /*优先级队列结点类*/
    public class PriorityNode extends Node{
    	public Object data;//结点数据域
    	public int priority;//结点优先级
    	public PriorityNode next;
    	
    	public PriorityNode() {
    		this(null,0,null);
    	}
    	
    	public PriorityNode(Object data, int priority) {
    		this(data,priority,null);
    	}
    	
    	public PriorityNode(Object x,int priority,PriorityNode next) {
    		this.data = x;
    		this.priority = priority;
    		this.next = next;
    	}
    }

### 优先级队列类 ###

package ch03;
    /*优先级队列描述类*/
    public class PriorityQueue implements IQueue {
    	private PriorityNode front;
    	private PriorityNode rear;
    	
    	@Override
    	public void clear() {
    		// TODO Auto-generated method stub
    		front = rear = null;
    	}
    
    	@Override
    	public boolean isEmpty() {
    		// TODO Auto-generated method stub
    		return front == null;
    	}
    
    	@Override
    	public int length() {
    		// TODO Auto-generated method stub
    		PriorityNode p = front;
    		int length = 0;
    		while(p!=null) {
    			p=p.next;
    			length++;
    		}
    		return 0;
    	}
    
    	@Override
    	public Object peek() {
    		// TODO Auto-generated method stub
    		if(isEmpty())
    			return null;
    		return front.data;
    	}
    
    	public void offer(Object x,int priority) throws Exception{
    		PriorityNode newNode = new PriorityNode(x,priority);
    		if(!isEmpty()) {
    			PriorityNode preNode = null;
    			PriorityNode currentNode = front;
    			while(currentNode!=null&&!(currentNode.priority<priority)) {
    				preNode = currentNode;
    				currentNode = currentNode.next;
    			}
    			if(currentNode==null) {
    				rear.next = newNode;
    				rear = newNode;
    			}else if(preNode==null) {
    				newNode.next = currentNode;
    				front=newNode;
    			}else {
    				preNode.next = newNode;
    				newNode.next = currentNode;
    			}
    		}else {
    			front=rear=newNode;
    		}
    		
    	}
    
    	@Override
    	public Object poll() {
    		// TODO Auto-generated method stub
    		if(isEmpty())
    			return null;
    		PriorityNode p = front;
    		front = front.next;
    		if(front==null)
    			front=rear=null;
    		return front.data;
    	}
    
    	@Override
    	public void display() {
    		// TODO Auto-generated method stub
    		if(!isEmpty()) {
    			for(PriorityNode p = front;p!=null;p=p.next) {
    				System.out.println(p.data+"\t"+p.priority);
    			}
    		}else {
    			System.out.println("空队列！");
    		}
    	}
    
    }

### 优先级队列测试代码 ###

package ch03;
    
    public class PriorityQueueDemo {
    
    	public static void main(String[] args) {
    		// TODO Auto-generated method stub
    		PriorityQueue p = new PriorityQueue();
    		try {
    			p.offer(1,20);
    			p.offer(2,30);
    			p.offer(3,10);
    			p.offer(4,50);
    		} catch (Exception e) {
    			// TODO Auto-generated catch block
    			e.printStackTrace();
    		}
    		System.out.println("出队列顺序为：");
    		p.display();
    	}
    
    }

##### 测试结果 #####

> 出队列顺序为：  
> 4 50  
> 2 30  
> 1 20  
> 3 10

### 参考类 ###

> [ch02.Node][]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDI3MDI0OA_size_16_color_FFFFFF_t_70]: /images/20220131/920c7b4661804cc4b2947a6df1067449.png
[20190515092624251.PNG]: /images/20220131/24a40d51ec1b4c3b9bec7ca048ca69ce.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDI3MDI0OA_size_16_color_FFFFFF_t_70 1]: /images/20220131/7f1112dcf2d2412baff92c0720f254f5.png
[ch02.Node]: https://blog.csdn.net/weixin_44270248/article/details/89365754