什么是队列结构：
队列是允许在一端进行插入操作，而在另一端进行删除操作的的线性表。
队列是一种先进先出的(First in First out)的线性表，简称为FIFO.允许插入的一端称为队尾，允许删除的一端称为队头。
如果从数据存储结构进一步划分,队列结构包括两类.
- 顺序队列存储结构:即使用一组地址连续的内存单元依次保存队列中的数据,在程序中,可以定义一个指定大小的结构数组作为队列.
- 即使用链表形式保存队列中各元素的值.
典型的队列结构如下图:
image
举两个生活中的例子。相信大家，在用电脑工作娱乐时，都会碰到这样的现象。当我们点击程序或进行其他操作时，电脑处于死机状态。正当我们准备Reset时，它突然像打了鸡血似的，突然把刚才我们的操作，按顺序执行了一遍。之所以会出现这个现象，是因为操作系统的多个程序，需要通过一个管道输出，而按先后顺序排队造成的。
还有有个例子，在我们打客服热线时，有时会出现等待的现象。当其他客户挂断电话，客服人员才会接通我们的电话。因为客服人员相对于客户而言，总是不够的，当客户量大于客服人员时，就会造成排队等待的想象。
操作系统、客服系统，都是应用了一种数据结构才实现了这种先进先出的排队功能，这个数据结构就是队列。
队列的基本操作一般只有两个:
- 入队列:将一个元素添加到队尾(相当于到队列最后排队等候)
- 出队列:将队头的元素依次取出,同时删除该元素,使后一个元素成为队头.
除了这两个主要的还有初始化队列,获取队列长度等简单操作.下面我们就分析怎么用java实现队列结构.
准备数据
static final int QUEUELEN = 15;
class DATA4
{
String name;
int age;
}
class SQType
{
DATA4 [] data = new DATA4[QUEUELEN]; //队列数组
int head; //队头
int tail; //队尾
}
首先我们定义了一个队列的最大长度QUEUELEN,然后定义了队列中结点的数据DATA4,SQType是我们定义的队列结构类.其中数组
data是用来保存队列数据的,head表示队列的队头,tail是表示队列的对尾,每一次添加一个元素的时候,就是入队列.我们把元素指向当前tail所指向的位置,tail所指向的就是队尾,现在原来队尾就是空的,现在添加元素了,我们把tail指向下一个空,我们取出数据的时候,也就是出队列.队头肯定是有数据的,所以我们直接通过head取出一个数据,然后把head指向下一个元素,也就是让下一个元素当队头.Ok,队列的入队列操作和出队列操作就是这样!下面我们开始吧
初始化队列机构
在使用顺序队列之前,首先要创建一个空的顺序结构,也就是初始化一个队列结构,步骤如下:
1.按符号常量QUEUELEN指定的大小申请一片内存空间,用来保存队列中的数据.
2.设置head=0,和tail=0,表示一个空栈.
代码如下:
public SQType SQTypeInit(){
SQType q;
if((q=new SQType())!=null){ //申请内存
q.head = 0; //设置队尾
q.tail = 0; //设置队尾
return q;
}else
{
return null; //返回null
}
}
在上诉代码,使用关键字new申请内存,申请成功后设置队头和队尾,然后返回申请内存的地址.如果申请内存失败,将返回null.
判断空队列
判断空队列即判断一个队列结构是否为空,只需要判断head==tail就可以了.空队列则不能在出队列.
public boolean SQTypeIsEmpty(SQType q){
if(q!=null){
return q.head ==q.tail;
}
return false;
}
判断满队列
判断一个队列是否为满,如果满队列,则表示该队列结构中没有多余的空间来保存额外数据,满了就不可以进行入队列操作,而可以进行出队列.
public boolean SQTypeIsFull(SQType q){
if(q!=null){
return q.tail == QUEUELEN;
}
return false;
}
清空队列
清空一个队列中所有的数据.
public void SQTypeClear(SQType q){
if(q!=null){
q.head = 0;
q.tail = 0;
}
}
释放空间
释放空间及释放队列结构所占用的内存单元.
public void SQTypeFree(SQType q){
if(q!=null){
q = null;
}
}
入队列
入队列是队列结构的基本操作.主要是把数据保存到队列结构中,步骤如下:
1.首先判断队列是否满了,如果队列满了,就算了
2.把当前数据元素指向现在的队尾tail
3.把tail=tail+1 ,向后移动一个位置.
public boolean SQTypeInsert(SQType q,DATA4 data){
if(!SQTypeIsFull(q)){ //判断队列是否满了
q.data[q.tail++] = data; //先入队列,后位置向后移动
return true; //入队列成功
}
return false; //入队列失败
}
出队列
出队列是队列结构的基本操作,主要把数据从队列结构中队头的位置推出来,步骤如下:
1.判断队列head,如果head等于tail,等表示为空队列.
2.从队列首部取出队头元素(实际是返回队头元素的引用)
3.设修改头head的序号,使其指向后一个元素.
public DATA4 SQTypeOut(SQType q){
if(!SQTypeIsEmpty(q)){ //判断队列是否为空
return q.data[q.head++]; //从队列取出数据,并且head指向下一个元素
}
return null;
}
读取结构数据
读结点数据的操作仅显示队列顶结点数据的内容,而出队列操作则将队顶数据弹出,该数据就不再不存在了.
public DATA4 SQTypePeek(SQType q){
if(!SQTypeIsEmpty(q)){ //判断队列是否为空
return q.data[q.head]; //从队列取出数据
}
return null;
}
计算队列长度
获取队列结构中结点的数据的个数.
public int SQTypeInt(SQType q){
int len = 0;
if(q!=null){
len = q.tail-q.head;
}
return len;
}
网友评论