java队列

  1. 云栖社区>
  2. 博客>
  3. 正文

java队列

mysoul8021 2018-11-19 23:59:15 浏览693
展开阅读全文

Java 实现队列

介绍

队列为特殊的线性表,队列的特点先进先出(FIFO),队列插入为入队,队列删除为出对。

Java 实现

这次使用顺序队列实现。(使用数组),
why?为什么不直接使用顺序表作为底层容器,因为入队操作执行顺序表尾插入,时间复杂度为O(1)

O(1) 普通语句,相互操作,时间复杂度为O(1)

出对操作执行表头删除操作,时间复杂度为O(n),因为涉及到一个循环遍历,移动,由于时间复杂度高,此时直接想方法将时间复杂度降低为O(1) ,即,用双指针解决。即front和rear两个解决

时间复杂度 O(n) 涉及一层循环,此时时间复杂度为O(n)

又因为直接更改下标,会导致空间的浪费,(出队操作)此时,为了减少空间的浪费,将队列设计为循环队列,目的,避免假满现象的出现。

空队列的时候 front = rear = 0
入队 front = 0 rear = 1
此时继续入队 front = 0 rear = 2
出队 front = rear = 2 两者相等
继续入队,front=2 rear = 3
不断的循环,总有一个为空,即rear
到队满 即 front = 2 rear = 1;
队满的判断 front = (rear + 1)% size
real永远为空

代码

接口

package demo.mingm.struct.queue;

/**
 * 接口 队列
* @author ming
* @date 2018/11/17
*/
public interface Queue<T> {
    // 定义数组长度
    public static final int DEFAULT_SIZE = 10;
    // 返回队列长度
    int size();
    // 判断队列是否为空
    boolean isEmpty();
    // 判断队列是否已满
    boolean isFull();
    // 入队, 成功true 错误false
    boolean add(T data);
    // offer 入队,和add方法不同的是,如果队满,或传入的为空,将会抛出错误,不会自动扩充
    boolean offer(T data);
    // 返回队头元素,不执行删除操作,为空 返回null
    T peek();
    // 返回队头元素,如果为空,将会抛出异常
    T element();
    // 出队,执行删除操作,若为空,返回null
    T poll();
    // 出队,执行删除操作,若为空,抛出异常
    T remove();
    // 清空队列
    void cleameQueue();
    
}

实现接口的类

package demo.mingm.struct.queue;
import java.util.Arrays;
import java.util.Vector;
public class SeqQueue<T> implements Queue<T> {
    private T[] elementData;    // 储存数据的数组
    private int size;    // 储存大小
    private int front, rear;    // 指针指向数组的元素,一个前,一个后
    private int real;
    
    public SeqQueue() {
        elementData= (T[]) new Object[DEFAULT_SIZE];
        // 指针的初始化
        this.front = 0;
        this.rear = 0;
        this.size = 0;
    }
    
    public SeqQueue(int length) {
        elementData = (T[]) new Object[length];
        this.front = 0;
        this.rear = 0;
        this.size = 0;
    }
    
    public int getSize() {
        return this.size;
    }
    
    public int getFront() {
        return this.front;
    }
    
    public int getRear() {
        return this.rear;
    }
    
    public void setSize(int size) {
        this.size = size;
    }
    
    public void setFront(int front) {
        this.front = front;
    }
    
    public void setRear(int rear) {
        this.rear = rear;
    }
    
    // 获取队列长度
    @Override
    public int size() {
        return this.getSize();
    }

    // 判断队列是否为空
    @Override
    public boolean isEmpty() {
        return this.getRear() == this.getFront();
    }
    
    // 判断队列是否已满
    @Override
    public boolean isFull() {
        return this.getFront() == (this.getRear() + 1) % this.elementData.length;
    }
    
    // 入队操作,如果不满,自动扩充数组
    @Override
    public boolean add(T data) {
        if(this.isFull()) {
            Arrays.copyOf(elementData, elementData.length*2);
        }
        // 是否插入空
        if(data == null)
            return false;
        // 添加data
        elementData[this.getRear()] = data;
        // 移动指针
        this.rear++;    // 创造单向队列
        this.size++;
        return true;
    }

    @Override
    public boolean offer(T data) {
        if(this.isFull() || data == null) {
            throw new NullPointerException("error 1");
        }
        // 添加data
        this.elementData[this.getRear()] = data;
        // 移动指针
        this.real = (this.real + 1)%elementData.length;    // 创造循环队列
        this.size++;
        return true;
    }

    // 返回队头元素,不删除
    @Override
    public T peek() {
        if(this.isEmpty())
            return null;
        return this.elementData[this.getFront()];
    }

    // 返回队头元素
    @Override
    public T element() {
        if(this.isEmpty())
            throw  new NullPointerException("error 2");
        return this.elementData[this.getFront()];
    }

    // 出队
    @Override
    public T poll() {
        if (this.isEmpty())
            return null;
        T tmp = this.peek();
        // 循环队列
        this.front = (this.getFront() + 1 ) % this.elementData.length;
        return tmp;
    }

    // 出队
    @Override
    public T remove() {
        if (this.isEmpty())
            throw  new NullPointerException("error 3");
        T tmp = this.peek();
        // 循环队列
        this.front = (this.getFront() + 1 ) % this.elementData.length;
        return tmp;
    }

    // 清空
    @Override
    public void cleameQueue() {
        this.real = 0;
        this.front = 0;
    }
}

www.iming.info

网友评论

登录后评论
0/500
评论
mysoul8021
+ 关注