java 数据结构与算法---队列

2018-06-18 01:00:57来源：未知阅读 ()

原理来自百度百科

一、队列的定义

队列是一种特殊的线性表，特殊之处在于它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作，和栈一样，队列是一种操作受限制的线性表。进行插入操作的端称为队尾，进行删除操作的端称为队头。队列中没有元素时，称为空队列。故队列又称为先进先出（FIFO—first in first out）线性表。

二、顺序队列

建立顺序队列结构必须为其静态分配或动态申请一片连续的存储空间，并设置两个指针进行管理。一个是队头指针front，它指向队头元素；另一个是队尾指针rear，它指向下一个入队元素的存储位置。

每次在队尾插入一个元素是，rear增1；每次在队头删除一个元素时，front增1。随着插入和删除操作的进行，队列元素的个数不断变化，队列所占的存储空间也在为队列结构所分配的连续空间中移动。当front=rear时，队列中没有任何元素，称为空队列。当rear增加到指向分配的连续空间之外时，队列无法再插入新元素，但这时往往还有大量可用空间未被占用，这些空间是已经出队的队列元素曾经占用过得存储单元。
顺序队列中的溢出现象：
（1） "下溢"现象：当队列为空时，做出队运算产生的溢出现象(数组已经为空了继续取出元素没有意义)。“下溢”是正常现象，常用作程序控制转移的条件。
（2）"真上溢"现象：当队列满时，继续做进栈运算产生空间溢出的现象(数组越界)。“真上溢”是一种出错状态，应设法避免。
（3）"假上溢"现象：由于头尾指针都不断前移，超出向量空间。这时整个向量空间及队列是空的却产生了"上溢"现象。

顺序队列的数组实现

package com.jalja.org.arith;

public class MySeQuence<E> {
    private Object [] arr;
    private int maxSize;
    private int index;//当前有效数据指针
    private int front;//队头指针front
    private int rear;//队尾指针rear
    
    public MySeQuence(int maxSize){
        this.arr=new Object[maxSize];
        this.front=0;
        this.rear=0;
        this.index=0;
        this.maxSize=maxSize;
    }
    //加入队列
    public void push(E e) {
        arr[rear]=e;
        rear++;
        index++;
    }
    //出队列
    public E pop() {
        if(isNull()) {
            throw new RuntimeException("MySeQuence is null");
        }
        E e=(E)arr[front];
        front++;
        index--;
        return e;
    }
    //查询队列内元素的个数
    public int getSize() {
        return index;
    }
    //判断队列是否为空
    public boolean isNull() {
        return front==rear;
    }
    //队列是否满了 true=满了 
    public boolean isFull() {
        return rear==maxSize;
    }
    public static void main(String[] args) {
        MySeQuence<Integer> myQueue=new MySeQuence<>(3);
        myQueue.push(1);
        myQueue.push(2);
        myQueue.push(3);
        System.out.println(String.format("元素个数:%s",myQueue.getSize()));
        System.out.println(String.format("队列是否满了:%s",myQueue.isFull()));
        while(!myQueue.isNull()) {
            System.out.println(myQueue.pop());
        }
        System.out.println(String.format("元素个数:%s",myQueue.getSize()));
        System.out.println(String.format("队列是否为空:%s",myQueue.isNull()));
    }
}

该实现会出现假上溢，当然这也是顺序队列的特点。我们一般使用循环队列解决这种问题。

三、循环队列

把队列空间想象成一个环形空间，环形空间中的存储单元循环使用，用这种方法管理的队列也就称为循环队列。

循环队列实现原理：

1、无论插入或删除，一旦rear指针增1或front指针增1 时超出了所分配的队列空间，就让它指向这片连续空间的起始位置,可用取余运算rear%MaxSize和front%MaxSize来实现。

2、在循环队列中，当队列为空时，有front=rear，而当所有队列空间全占满时，也有front=rear。为了区别这两种情况，规定循环队列最多只能有MaxSize+1个队列元素，当循环队列中只剩下一个空存储单元时，队列就已经满了；因此，队列判空的条件时front=rear，而队列判满的条件时front=rear%MaxSize。

循环队列数组的实现

package com.jalja.org.arith;

public class MyCirQuence<E> {
    private Object [] arr;
    private int maxSize;
    private int index;//当前有效数据指针
    private int front;//队头指针front
    private int rear;//队尾指针rear
    
    public MyCirQuence(int maxSize){
        this.arr=new Object[maxSize+1];
        this.front=0;
        this.rear=0;
        this.index=0;
        this.maxSize=maxSize;
    }
    //加入队列   在除法计算中   余数一定要比除数小  
    public void push(E e) {
        if(isFull()) {
            throw new RuntimeException("MySeQuence is full");
        }
        arr[rear%maxSize]=e; //数组的下表在循环 rear%maxSize
        rear++;//real 一直在增加 
        index++;
    }
    //出队列  余数一定要比除数小 
    public E pop() {
        if(isNull()) {
            throw new RuntimeException("MySeQuence is null");
        }
        E e=(E)arr[front%maxSize];
        front++;
        index--;
        return e;
    }
    //查询队列内元素的个数
    public int getSize() {
        return index;
    }
    //判断队列是否为空
    public boolean isNull() {
        return front==rear;
    }
    //队列是否满了 true=满了 
    public boolean isFull() {
        return !isNull() && front==rear%maxSize;
    }
    public static void main(String[] args) {
        MyCirQuence<Integer> myQueue=new MyCirQuence<>(3);
        myQueue.push(1);
        myQueue.push(2);
        myQueue.push(3);

        System.out.println("==>:"+myQueue.pop());
        System.out.println("==>:"+myQueue.pop());
        System.out.println("==>:"+myQueue.pop());
       
        myQueue.push(4);
        myQueue.push(5);
        myQueue.push(6);
        
        while(!myQueue.isNull()) {
            System.out.println(myQueue.pop());
        }
        
    }
}