java隊列

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