java算法----队列(循环顺序队列)

算法,一门既不容易入门,也不容易精通的学问。但是作为一条有梦想的咸鱼,我决定努力一大把。

栈与队列分别是两种数据结构,不同语言对于栈和队列有着不同的声明,在 java 中 Stack 类是继承自 Vector 集合的子类,Queue 则是以接口形式存在,常用的其实现类是 LinkedList 这个双向队列。在java的标准模版库也是有这两个数据结构定义的具体类的。

栈数据结构的特点是 FILO(first in last out) 即先进后出,队列则是 FIFO(first in first out)即先进先出。

日常现实生活中处处可见,比如,学生在食堂买饭、在公交车上车排队等。这些排队规律都是先来先处理事件,都不能插队,要遵守一定的规范。其实。我们常用的计算机也有队列,操作系统中的进程、资源等待队列、作业队列等等。

​​​​​​

一、队列的概念:

  队列(简称作队,Queue)也是一种特殊的线性表,队列的数据元素以及数据元素间的逻辑关系和线性表完全相同,其差别是线性表允许在任意位置插入和删除,而队列只允许在其一端进行插入操作在其另一端进行删除操作

队列中允许进行插入操作的一端称为队尾,允许进行删除操作的一端称为队头。队列的插入操作通常称作入队列,队列的删除操作通常称作出队列

下图是一个依次向队列中插入数据元素a0,a1,...,an-1后的示意图:

java算法----队列(循环顺序队列)

 

1、顺序队列的“假溢出”:

java算法----队列(循环顺序队列)

上图中,front指针指向队头元素,rear指针指向队尾元素的下一个位置。图(d)中b、c、d出队后,front指针指向元素e,rear指针在数组外面。假设这个队列的总个数不超过5个,但目前如果接着入队的话,因数组末尾元素已经被占用,再向后加就会产生数组越界的错误,可实际上队列在下标为0、1、2、3、4的地方还是空闲的,我们把这种现象叫做“假溢出”。

2、循环顺序队列:

    所以解决假溢出的办法就是后面满了,就再从头开始,也就是头尾相接的循环。我们把队列的这种逻辑上首尾相连的顺序存储结构称为循环队列:

        当队列空时,条件就是from = rear,当队列满时,我们修改其条件,保留一个元素空间。也就是说,队列满时,数组中还有一个空闲单元。 如下图所示,我们就认为此队列已经满了,

 

java算法----队列(循环顺序队列)

由于rear可能比front大,也可能比front小,所以尽管它们只相差一个位置时就是满的情况,但也可能是相差整整一圈。所以若队列的最大尺寸为QueueSize,那么队列满的条件是(rear+1) %QueueSize == front (取模“%的目的就是为了整合rear与front大小为一个问题)。

比如上面这个例子, QueueSize = 5,当 front=0,而 rear=4, (4+1) %5 = 0,所以此时队列满。再比如,front = 2而rear =1。(1 + 1) %5 = 2,所以此时 队列也是满的。而对于下图, front = 2而rear= 0, (0+1) %5 = 1,1!=2,所以此时队列并没有满。

java算法----队列(循环顺序队列)

另外,当rear > front时,此时队列的长度为rear—front。但当rear < front时,队列长度分为两段,一段是QueueSize-front,另一段是0 + rear,加在一起,队列长度为rear-front + QueueSize,

因此通用的计算队列长度公式为:

(rear—front + QueueSize) % QueueSize

总结

队空条件:front == rear

队满条件:(rear+1) %QueueSize == front

队列长度:(rear—front + QueueSize) % QueueSize

循环队列基本操作的实现

接口类

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();
}

入队操作

    public void offer(Object x) throws Exception {
        if ((rear+1)%queueElem.length==front)            //队列满
            throw  new Exception("队列已满");            //抛出异常
        else {
            queueElem[rear]=x;
                                          //x存入rear所指数组存储位置,使其成为队尾
            rear=(rear+1)%queueElem.length;            //修改队尾指针
        }
    }

出队

 public Object poll() {
        if (front==rear)
        return null;
        else{
            Object t=queueElem[front];
            front=(front+1)%queueElem.length;
            return t;                        //返回队列的队首元素
        }

代码总结


public class CircleSqQueue implements IQueue{
    private  Object[] queueElem;//队列存储空间
    private  int front;         //队首的引用
    private int rear;      //队尾 的引用

    public CircleSqQueue(int maxSize) {
        front=rear=0;                  //队尾、队首初始化尾0
      queueElem = new Object[maxSize];//尾队列分配maxSize个储存单元
    }

    @Override
    public void clear() {
        front=rear=0;//
    }

    @Override
    public boolean isEmpty() {
        return front==rear;
    }

    @Override
    public int length() {
        return (rear-front+queueElem.length)%queueElem.length;
    }
        //读取队首元素
    @Override
    public Object peek() {
        if (front==rear)

        return null;
        else
            return queueElem[front];
    }
//入队操作
    @Override
    public void offer(Object x) throws Exception {
        if ((rear+1)%queueElem.length==front)
            throw  new Exception("队列已满");
        else {
            queueElem[rear]=x;
            //x存入rear所指数组存储位置,使其成为队尾
            rear=(rear+1)%queueElem.length;//修改队尾指针
        }
    }

    @Override
    public void display() {
        //简单的遍历
        if(!isEmpty()) {
            for (int i=front;i!=rear;i=(i+1)%queueElem.length)
                System.out.print(queueElem[i].toString()+"\t");
        }else{
        }
        //思路从front开始遍历,遍历时候要遍历多少个元素就可以了
        //要求出当前队列的个数
        
    }
//出队操作
    @Override
    public Object poll() {
        if (front==rear)
        return null;
        else{
            Object t=queueElem[front];
            front=(front+1)%queueElem.length;
            return t;        //返回队列的队首元素
        }
        
        }
    }

用循环加switch  case写个测试类,测试成功!

java算法----队列(循环顺序队列)java算法----队列(循环顺序队列)

 java算法----队列(循环顺序队列)java算法----队列(循环顺序队列)

 

 

 

上一篇:容器:deque用法及示例


下一篇:基于循环链表的队列的基本操作