java隊(duì)列

沈建明發(fā)布于2019-08-16 13:45 / 692人閱讀

摘要：實(shí)現(xiàn)隊(duì)列介紹隊(duì)列為特殊的線性表，隊(duì)列的特點(diǎn)先進(jìn)先出，隊(duì)列插入為入隊(duì)，隊(duì)列刪除為出對(duì)。實(shí)現(xiàn)這次使用順序隊(duì)列實(shí)現(xiàn)。

Java 實(shí)現(xiàn)隊(duì)列

介紹

隊(duì)列為特殊的線性表，隊(duì)列的特點(diǎn)先進(jìn)先出（FIFO），隊(duì)列插入為入隊(duì)，隊(duì)列刪除為出對(duì)。

Java 實(shí)現(xiàn)

這次使用順序隊(duì)列實(shí)現(xiàn)。（使用數(shù)組），
why？為什么不直接使用順序表作為底層容器，因?yàn)槿腙?duì)操作執(zhí)行順序表尾插入，時(shí)間復(fù)雜度為O(1)

O(1) 普通語句，相互操作，時(shí)間復(fù)雜度為O(1)

出對(duì)操作執(zhí)行表頭刪除操作，時(shí)間復(fù)雜度為O(n)，因?yàn)樯婕暗揭粋€(gè)循環(huán)遍歷，移動(dòng)，由于時(shí)間復(fù)雜度高，此時(shí)直接想方法將時(shí)間復(fù)雜度降低為O(1) ，即，用雙指針解決。即front和rear兩個(gè)解決

時(shí)間復(fù)雜度 O(n) 涉及一層循環(huán)，此時(shí)時(shí)間復(fù)雜度為O(n)

又因?yàn)橹苯痈南聵?biāo)，會(huì)導(dǎo)致空間的浪費(fèi)，（出隊(duì)操作）此時(shí)，為了減少空間的浪費(fèi)，將隊(duì)列設(shè)計(jì)為循環(huán)隊(duì)列，目的，避免假滿現(xiàn)象的出現(xiàn)。

空隊(duì)列的時(shí)候 front = rear = 0
入隊(duì) front = 0 rear = 1
此時(shí)繼續(xù)入隊(duì) front = 0 rear = 2
出隊(duì) front = rear = 2 兩者相等
繼續(xù)入隊(duì)，front=2 rear = 3
不斷的循環(huán)，總有一個(gè)為空，即rear
到隊(duì)滿即 front = 2 rear = 1；
隊(duì)滿的判斷 front = （rear + 1）% size
real永遠(yuǎn)為空

代碼接口

package demo.mingm.struct.queue;

/**
 * 接口 隊(duì)列
* @author ming
* @date 2018/11/17
*/
public interface Queue {
    // 定義數(shù)組長度
    public static final int DEFAULT_SIZE = 10;
    // 返回隊(duì)列長度
    int size();
    // 判斷隊(duì)列是否為空
    boolean isEmpty();
    // 判斷隊(duì)列是否已滿
    boolean isFull();
    // 入隊(duì)， 成功true 錯(cuò)誤false
    boolean add(T data);
    // offer 入隊(duì)，和add方法不同的是，如果隊(duì)滿，或傳入的為空，將會(huì)拋出錯(cuò)誤，不會(huì)自動(dòng)擴(kuò)充
    boolean offer(T data);
    // 返回隊(duì)頭元素，不執(zhí)行刪除操作，為空 返回null
    T peek();
    // 返回隊(duì)頭元素，如果為空，將會(huì)拋出異常
    T element();
    // 出隊(duì)，執(zhí)行刪除操作，若為空，返回null
    T poll();
    // 出隊(duì)，執(zhí)行刪除操作，若為空，拋出異常
    T remove();
    // 清空隊(duì)列
    void cleameQueue();
    
}

實(shí)現(xiàn)接口的類

package demo.mingm.struct.queue;
import java.util.Arrays;
import java.util.Vector;
public class SeqQueue implements Queue {
    private T[] elementData;    // 儲(chǔ)存數(shù)據(jù)的數(shù)組
    private int size;    // 儲(chǔ)存大小
    private int front, rear;    // 指針指向數(shù)組的元素，一個(gè)前，一個(gè)后
    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;
    }
    
    // 獲取隊(duì)列長度
    @Override
    public int size() {
        return this.getSize();
    }

    // 判斷隊(duì)列是否為空
    @Override
    public boolean isEmpty() {
        return this.getRear() == this.getFront();
    }
    
    // 判斷隊(duì)列是否已滿
    @Override
    public boolean isFull() {
        return this.getFront() == (this.getRear() + 1) % this.elementData.length;
    }
    
    // 入隊(duì)操作，如果不滿，自動(dòng)擴(kuò)充數(shù)組
    @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;
        // 移動(dòng)指針
        this.rear++;    // 創(chuàng)造單向隊(duì)列
        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;
        // 移動(dòng)指針
        this.real = (this.real + 1)%elementData.length;    // 創(chuàng)造循環(huán)隊(duì)列
        this.size++;
        return true;
    }

    // 返回隊(duì)頭元素，不刪除
    @Override
    public T peek() {
        if(this.isEmpty())
            return null;
        return this.elementData[this.getFront()];
    }

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

    // 出隊(duì)
    @Override
    public T poll() {
        if (this.isEmpty())
            return null;
        T tmp = this.peek();
        // 循環(huán)隊(duì)列
        this.front = (this.getFront() + 1 ) % this.elementData.length;
        return tmp;
    }

    // 出隊(duì)
    @Override
    public T remove() {
        if (this.isEmpty())
            throw  new NullPointerException("error 3");
        T tmp = this.peek();
        // 循環(huán)隊(duì)列
        this.front = (this.getFront() + 1 ) % this.elementData.length;
        return tmp;
    }

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