队列(Queue)--环形队列、优先队列和双向队列

时间:2021-10-24 08:40:49

1. 队列概述

队列和堆栈都是有序列表,属于抽象型数据类型(ADT),所有加入和删除的动作都发生在不同的两端,并符合First In, First Out(先进先出)的特性。

特性:

·FIFO

·拥有两种基本操作,即加入与删除,而且使用front与rear两个指针来分别执行队列的前端与尾端。

如定义int[] queue= new int[int max];

当rear为max-1时,认为队列已满(Queue-Full),新的数据不能再加入。此时可以将队列中的数据往前挪移,移除空间让新数据加入。

这种在队列中移动数据的做法虽可以解决队列空间浪费的问题,但如果队列中的数据过多时,将会造成时间的浪费。

以链表实现队列:

class QueueNode{
int data;
QueueNode next;
public QueueNode(int data){
this.data = data;
next = null;
}
} class Linked_List_Queue {
public QueueNode front;
public QueueNode rear; public Linked_List_Queue(){front=null; rear=null;} //队列数据的存入
public Boolean enqueue(int value){
QueueNode node = new QueueNode(value);
if(rear==null) front=node;
else
rear.next = node;
rear= node;
return true;
} public int dequeue(){
int value;
if(!(front==null)){
if(front==rear) rear=null;
value = front.data;
front = front.next;
return value;
} else return -1;
}
}

队列在计算机领域的应用:

1. 在图形遍历的先广后深搜索法(BFS)

2. 用于计算机的模拟(simulation)

3. CPU的工作调度等。

2.环形队列

线性队列有空间浪费的问题,可以利用环形队列来解决。它是Q(0:n-1)的一维数组,同事Q(0)为Q(n-1)的下一个元素。

其中,指针front用于以逆时针方向指向队列中第一个元素的前一个位置,rear则指向队列当前的最后位置。一开始front和rear均预设为-1,表示为空队列。也就是说

如果front=rear则为空队列。

这样设计的好处是,环形队列为空队列和满队列时,front和rear都会指向同一个地方。为更方便我们判断,我们仅允许队列最多存放n-1个数据(亦即牺牲最后一个空间),

当rear指针的下一个是front的位置时,就认定队列已满,无法再将数据加入。所以一个Q(0:n-1)的环形队列最多只能放n-1个元素。

3.优先队列

优先队列(priority queue)为一种不必遵守队列特性--FIFO的有序表,其中的每一个元素都赋予一个优先权(Priority),加入元素时可任意加入,但有最高优先权者(Highest Priority Out First, HPOF)则最先输出。

在计算机中CPU的工作调度,优先权调度(Priority Scheduling, PS)就是一种挑选任务的“调度算法”(Scheduling Aalgotithm),也会使用到优先队列。级别高的用户,就比一般用户拥有较高的权利。

当各元素以输入先后次序为优先权时,就是一般的队列,假如是以输入先后次序作为最不优先权时,此优先队列即为一堆栈。

4.双向队列

双向队列(Double-ends Queues),是一种前后两段都可输入或读取数据的有序表。

在双向队列中,我们仍使用两个指针,分别指向加入及取回端,只是加入和取回数据时,各指针所扮演的角色不再是固定的加入或取回。而且两边的指针都向队列*移动,其他部分则和一般队列无异。

code加入个人github:interesting_code中。