Java動態循環隊列是如何實現的

一、隊列

1.1 定義

隊列 (Queue) 是一種限定性的有序線性表,它隻允許在表的一端插入元素,而在另一端刪除元素,所以隊列具有先進先出 (Fist In Fist Out,縮寫為FIFO)的特性。

  • 在隊列中,允許插入的一端叫做隊尾(rear);
  • 允許刪除的一端則稱為隊頭(front)。
  • 隊列是一個有序列表,可以用數組或是鏈表來實現。
  • 遵循先進先出的原則。即:先存入隊列的數據,要先取出。

1.2 抽象數據類型

數據元素:可以是任意類型的數據,但必須屬於同一個數據對象。

關系:隊列中數據元素之間是線性關系。

基本操作:

1.初始化操作。使用構造方法設置一個空隊列。

2.isEmpty():判空操作。若隊列為空,則返回TRUE,否則返回FALSE。

3.isFull():判滿操作。若隊列為滿,則返回TRUE,否則返回FALSE。

4.getSize():獲取隊列元素個數。

5.add(E e):進隊操作。在隊列Q的隊尾插入e。如果隊滿,拋出異常。

6.poll():出隊操作。使隊列Q的隊頭元素出隊,並用e返回其值。如果隊空,拋出異常。

7.getHead ():取隊頭元素操作。用e取得隊頭元素的值。如果隊列為空,則返回null。

8.clear():隊列置空操作。將隊列Q置為空隊列。

9.destroy():隊列銷毀操作。釋放隊列的空間。

1.3 順序存儲

隊列的一種順序存儲稱為順序隊列。與順序棧類似,在隊列的順序存儲結構中,用一組地址連續的存儲單元依次存放從隊頭到隊尾的元素,如一維數組Queue[maxSize]。

二、數組隊列

由於隊列中隊頭和隊尾的位置都是動態變化的,因此需要附設兩個指針 front和 rear。

  • front:指示隊頭元素在數組中的位置;
  • rear:指示真實隊尾元素相鄰的下一個位置。

2.1 思路分析

  • 初始化隊列時,令front = rear = 0
  • 判斷隊空的條件:front == rear
  • 判斷隊滿的條件:rear == maxSize
  • 入隊時,若尾指針rear 小於隊列的最大下標 maxSize,則將數據存入rear所指的數組元素中,否則無法存入數據;然後將尾指針往後移: rear + 1
  • 出隊時,若隊列不為空,取出隊頭指針front所指的元素;然後將尾指針往後移: front + 1

2.2 代碼實現

定義接口方法:

/**
 * description:自定義隊列接口
 *
 * @author RenShiWei
 * Date: 2021/5/29 20:45
 **/
public interface Queue<E> {

    /**
     * @return 是否隊空
     */
    boolean isEmpty();

    /**
     * @return 是否隊滿
     */
    boolean isFull();

    /**
     * @return 隊列的可承載元素個數
     */
    int getCapacity();

    /**
     * @return 隊列元素個數
     */
    int getSize();

    /**
     * 隊尾入隊
     *
     * @param e 入隊元素
     */
    void add(E e);

    /**
     * 隊首出隊
     *
     * @return 出隊元素
     */
    E poll();

    /**
     * 獲取隊首元素
     *
     * @return 隊首元素
     */
    E getHead();

}

2.3 數組隊列實現

/**
 * description:數組隊列
 *
 * @author RenShiWei
 * Date: 2021/5/29 20:41
 **/
public class ArrayQueue<E> implements Queue<E> {

    /** 表示可存儲元素的最大容量 */
    private int maxSize;
    /** 隊列頭 */
    private int front;
    /** 隊列尾 */
    private int rear;
    /** 該數據用於存放數據,模擬隊列 */
    private E[] data;

    /**
     * 初始化隊列
     *
     * @param arrMaxSize 初始隊列最大容量
     */
    @SuppressWarnings("unchecked")
    public ArrayQueue(int arrMaxSize) {
        maxSize = arrMaxSize;
        data = (E[]) new Object[maxSize];
        front = 0;
        rear = 0;
    }

    /**
     * @return 是否隊空
     */
    @Override
    public boolean isEmpty() {
        return front == rear;
    }

    /**
     * @return 是否隊滿
     */
    @Override
    public boolean isFull() {
        return rear == maxSize;
    }

    /**
     * @return 隊列元素個數
     */
    @Override
    public int getSize() {
        return rear - front;
    }

    /**
     * 隊尾入隊
     *
     * @param e 入隊元素
     */
    @Override
    public void add(E e) {
        if (isFull()) {
            throw new IllegalArgumentException("隊列已滿,不能入隊!");
        }
        data[rear++] = e;
    }

    /**
     * 隊首出隊
     *
     * @return 出隊元素
     */
    @Override
    public E poll() {
        if (isEmpty()) {
            throw new IllegalArgumentException("隊列為空,不能出隊!");
        }
        //出隊位置置null
        E temp = data[front];
        data[front++] = null;
        return temp;
    }

    /**
     * 獲取隊首元素
     * 如果隊空,返回null
     *
     * @return 隊首元素
     */
    @Override
    public E getHead() {
        return data[front];
    }

    /**
     * @return 隊列的可承載元素個數
     */
    @Override
    public int getCapacity() {
        return data.length - 1;
    }

    /**
     * @return 隊列的有效容量(未使用的空間數量)
     */
    public int getEmptyCount() {
        return maxSize - rear;
    }

    @Override
    public String toString() {
        StringBuilder res = new StringBuilder();
        res.append("Queue: ");
        res.append("front [");
        for (int i = front; i < rear; i++) {
            res.append(data[i]);
            if (i != rear - 1) {
                res.append(", ");
            }
        }
        res.append("] rear");
        return res.toString();
    }

    /**
     * 隊列測試
     */
    public static void main(String[] args) {
        ArrayQueue<Integer> queue = new ArrayQueue<>(5);
        Scanner sc = new Scanner(System.in);
        char c;
        boolean loop = true;
        while (loop) {
            System.out.println("s(toString):輸出隊列");
            System.out.println("e(exit):退出程序");
            System.out.println("a(add):添加數據到隊列");
            System.out.println("p(poll):從隊列取出數據");
            System.out.println("h(getHead):查看隊列頭的數據");
            System.out.println("n(isEmpty):是否隊空");
            System.out.println("f(isFull):是否隊滿");
            c = sc.next().charAt(0);
            switch (c) {
                case 's':
                    System.out.println("當前隊列:" + queue.toString() + "\t元素個數:" + queue.getSize() + "\t有效容量:" + queue.getEmptyCount());
                    break;
                case 'e':
                    sc.close();
                    loop = false;
                    break;
                case 'a':
                    System.out.println("請輸入一個整數");
                    queue.add(sc.nextInt());
                    break;
                case 'p':
                    System.out.printf("出隊元素:%d\n", queue.poll());
                    break;
                case 'h':
                    System.out.printf("隊首元素:%d\n", queue.getHead());
                    break;
                case 'n':
                    System.out.println("隊空:" + queue.isEmpty());
                    break;
                case 'f':
                    System.out.println("隊滿:" + queue.isFull());
                    break;
                default:
                    break;
            }
        }
        System.out.println("程序退出");
    }

}

2.4 分析

假溢出現象

在非空順序隊列中,隊頭指針始終指向當前的隊頭元素,而隊尾指針始終指向真正隊尾元素。當rear == maxSize - 1 時,認為隊滿。但此時不一定是真的隊滿,因為隨著部分元素的出隊,數組前面會出現一些空單元,如下圖所示。由於隻能在隊尾入隊,使得上述空單元無法使用。把這種現象稱為假溢出

image-20210529183259424

問題:目前這個數組使用一次就不能用(出隊的空間),沒有達到復用的效果。可使用算法將其改造成環形隊列(取模:%)。

三、環形隊列

為瞭解決假溢出現象並使得隊列空間得到充分利用,一個較巧妙的辦法是將順序隊列的數組看成一個環狀的空間,即規定最後一個單元的後繼為第一個單元,我們形象地稱之為循環隊列。

3.1 思路分析

  • 初始化隊列時,令front = rear = 0front指向隊列的第一個元素,rear指向隊列最後一個元素的後一個位置(希望損失一個位置作為約定,用來區分隊空和隊滿)。
  • 判斷隊空的條件:front == rear
  • 判斷隊滿的條件:(rear + 1) % maxSize == front
  • 隊列中的元素個數:(rear + maxSize - front) % maxSize
  • 入隊時,將數據存入rear所指的數組元素中,指針變化:rear = ( rear+1) % maxSize
  • 出隊時,將數據存入front所指的數組元素中,指針變化:front = ( front+1 ) % maxSize

下圖給出瞭循環隊列的幾種情況:

image-20210530163134963 

3.2 代碼實現

/**
 * description:循環隊列
 *
 * @author RenShiWei
 * Date: 2021/5/30 16:38
 **/
public class LoopQueue<E> implements Queue<E> {

    /** 存儲元素 數組的長度(有效長度需要-1) */
    private int maxSize;
    /** 隊列頭 */
    private int front;
    /** 隊列尾 */
    private int rear;
    /** 該數據用於存放數據,模擬隊列 */
    private E[] data;

    /**
     * 初始化環形隊列
     *
     * @param arrMaxSize 初始隊列容量
     */
    @SuppressWarnings("unchecked")
    public LoopQueue(int arrMaxSize) {
        //循環隊列需要有意識浪費一個空間
        maxSize = arrMaxSize + 1;
        data = (E[]) new Object[maxSize];
    }

    /**
     * @return 是否隊空
     */
    @Override
    public boolean isEmpty() {
        return front == rear;
    }

    /**
     * @return 是否隊滿
     */
    @Override
    public boolean isFull() {
        return (rear + 1) % maxSize == front;
    }

    /**
     * @return 隊列的可承載元素個數
     */
    @Override
    public int getCapacity() {
        return data.length - 1;
    }

    /**
     * @return 隊列元素個數
     */
    @Override
    public int getSize() {
        return (rear + maxSize - front) % maxSize;
    }

    /**
     * 隊尾入隊
     *
     * @param e 入隊元素
     */
    @Override
    public void add(E e) {
        if (isFull()) {
            throw new IllegalArgumentException("隊列已滿,不能入隊!");
        }
        data[rear] = e;
        //rear指針後移一位
        rear = (rear + 1) % maxSize;
    }

    /**
     * 隊首出隊
     *
     * @return 出隊元素
     */
    @Override
    public E poll() {
        if (isEmpty()) {
            throw new IllegalArgumentException("隊列為空,不能出隊!");
        }
        E temp = data[front];
        //出隊位置置null
        data[front] = null;
        //front指針後移一位
        front = (front + 1) % maxSize;
        return temp;
    }

    /**
     * 獲取隊首元素
     * 如果隊空,返回null
     *
     * @return 隊首元素
     */
    @Override
    public E getHead() {
        return data[front];
    }

    @Override
    public String toString() {
        StringBuilder res = new StringBuilder();
        res.append(String.format("Queue: size = %d , capacity = %d\n", getSize(), getCapacity()));
        res.append("front [");
        for (int i = front; i != rear; i = (i + 1) % data.length) {
            res.append(data[i]);
            if ((i + 1) % data.length != rear) {
                res.append(", ");
            }
        }
        res.append("] tail");
        return res.toString();
    }

    /**
     * 隊列測試
     */
    public static void main(String[] args) {
        LoopQueue<Integer> queue = new LoopQueue<>(5);
        Scanner sc = new Scanner(System.in);
        char c;
        boolean loop = true;
        while (loop) {
            System.out.println("s(toString):輸出隊列");
            System.out.println("e(exit):退出程序");
            System.out.println("a(add):添加數據到隊列");
            System.out.println("p(poll):從隊列取出數據");
            System.out.println("h(getHead):查看隊列頭的數據");
            System.out.println("n(isEmpty):是否隊空");
            System.out.println("f(isFull):是否隊滿");
            c = sc.next().charAt(0);
            switch (c) {
                case 's':
                    System.out.println("當前隊列:" + queue.toString());
                    break;
                case 'e':
                    sc.close();
                    loop = false;
                    break;
                case 'a':
                    System.out.println("請輸入一個整數");
                    queue.add(sc.nextInt());
                    break;
                case 'p':
                    System.out.printf("出隊元素:%d\n", queue.poll());
                    break;
                case 'h':
                    System.out.printf("隊首元素:%d\n", queue.getHead());
                    break;
                case 'n':
                    System.out.println("隊空:" + queue.isEmpty());
                    break;
                case 'f':
                    System.out.println("隊滿:" + queue.isFull());
                    break;
                default:
                    break;
            }
        }
        System.out.println("程序退出");
    }


}

3.3 分析

相比數組隊列來說,循環隊列解決瞭數組空間不能再次利用的問題。但依然存在一些問題:

  • 當隊列真的滿的時候就不能再進行入隊操作瞭。但是從我們常用的ArrayList來分析,在存儲空間允許的條件下是可以一直添加元素的。
  • 當數組元素頻繁進行入隊或者出隊操作時,可能造成空間的浪費。循環隊列其實隻利用瞭有限的存儲空間,但是在最初實例化循環隊列的時候,如果空間聲明的很大,那麼會造成一定程度上的空間浪費。
  • 假設,聲明一個容量為20的循環隊列,但每次入隊2個元素後,又出隊2個元素,那麼實際隻利用瞭很有限的空間,造成瞭空間浪費,但又不能聲明的空間太小,並不能保證未來每次隻入隊或者出隊2個元素。

因此,是否可以實現動態的將循環隊列進行擴容或者縮容,上述兩個問題,可以利用下面的動態循環隊列來實現。

當然,上述的數組隊列,也可以改造成動態的,但是出隊元素的空間依然會浪費,所以沒必要進行實現。

四、動態循環隊列

為瞭解決循環隊列,隊滿不能入隊,以及頻繁入隊出隊引起的空間浪費,而引出動態循環隊列的概念。即在隊滿時進行擴容,在隊列元素個數下降到一定情況下進行縮容

4.1 思路分析

  • 除瞭入隊和出隊操作,其他操作均與循環隊列相同。
  • 循環隊列存儲元素的數組容量變更思路:使用擴容一倍/縮容一倍的新數組接收原來循環隊列存儲的元素。接收後,將front指針置為0;將rear指針值到最後一個元素的位置(即存儲有效元素的數量)。
  • 什麼時候擴容:隊滿
  • 什麼時候縮容:隊列元素隻有1/4,並且縮容後容量不為0。
  • 數組容量為0時,縮容會出現異常
  • 為什麼不在隊列元素隻有1/2時縮容?當數組元素為一半的時候一次添加,一次刪除,造成的一直擴容和減小的操作

4.2 代碼實現

/**
 * description:動態循環
 *
 * @author RenShiWei
 * Date: 2021/5/30 17:06
 **/
public class DynamicLoopQueue<E> implements Queue<E> {

    /** 存儲元素 數組的長度(有效長度需要-1) */
    private int maxSize;
    /** 隊列頭 */
    private int front;
    /** 隊列尾 */
    private int rear;
    /** 該數據用於存放數據,模擬隊列 */
    private E[] data;

    /**
     * 初始化環形隊列
     *
     * @param arrMaxSize 初始隊列容量
     */
    @SuppressWarnings("unchecked")
    public DynamicLoopQueue(int arrMaxSize) {
        //循環隊列需要有意識浪費一個空間
        maxSize = arrMaxSize + 1;
        data = (E[]) new Object[maxSize];
    }

    /**
     * @return 是否隊空
     */
    @Override
    public boolean isEmpty() {
        return front == rear;
    }

    /**
     * @return 是否隊滿
     */
    @Override
    public boolean isFull() {
        return (rear + 1) % maxSize == front;
    }

    /**
     * @return 隊列的可承載元素個數
     */
    @Override
    public int getCapacity() {
        return data.length - 1;
    }

    /**
     * @return 隊列元素個數
     */
    @Override
    public int getSize() {
        return (rear + maxSize - front) % maxSize;
    }

    /**
     * 隊尾入隊
     *
     * @param e 入隊元素
     */
    @Override
    public void add(E e) {
        if (isFull()) {
            //隊滿不再進行報錯,而是進行動態擴容
            resize(getCapacity() * 2);
        }
        data[rear] = e;
        //rear指針後移一位
        rear = (rear + 1) % maxSize;
    }

    /**
     * 隊首出隊
     *
     * @return 出隊元素
     */
    @Override
    public E poll() {
        if (isEmpty()) {
            throw new IllegalArgumentException("隊列為空,不能出隊!");
        }
        E temp = data[front];
        //出隊位置置null
        data[front] = null;
        //front指針後移一位
        front = (front + 1) % maxSize;

        //當數組實際元素減小到空間的一半的時候,對其進行縮小
        //if(size == data.length / 2)
        /*
            解決當一半的時候一次添加,一次刪除,造成的一直擴容和減小的操作,
            增加必須要擴容,所以可以讓縮容變得更懶時在進行,即1/4時
            data.length / 2 != 0防止數組大小最後變成0,造成異常
        */
        if (getSize() == getCapacity() / 4 && getCapacity() / 2 != 0) {
            resize(getCapacity() / 2);
        }
        return temp;
    }

    /**
     * 獲取隊首元素
     * 如果隊空,返回null
     *
     * @return 隊首元素
     */
    @Override
    public E getHead() {
        return data[front];
    }

    /**
     * 擴容方法
     *
     * @param newCapacity 擴容後的隊列大小
     */
    @SuppressWarnings("unchecked")
    private void resize(int newCapacity) {
        E[] newData = (E[]) new Object[newCapacity + 1];
        //有多個元素循環多少次
        for (int i = 0; i < getSize(); i++) {
            //循環隊列會發生偏移,重新賦值給新數組
            newData[i] = data[(i + front) % data.length];
        }
        data = newData;
        maxSize = data.length;
        //重置指針
        front = 0;
        rear = getSize();
    }

    @Override
    public String toString() {
        StringBuilder res = new StringBuilder();
        res.append(String.format("Queue: size = %d , capacity = %d\n", getSize(), getCapacity()));
        res.append("front [");
        for (int i = front; i != rear; i = (i + 1) % data.length) {
            res.append(data[i]);
            if ((i + 1) % data.length != rear) {
                res.append(", ");
            }
        }
        res.append("] tail");
        return res.toString();
    }

    /**
     * 隊列測試
     */
    public static void main(String[] args) {
        DynamicLoopQueue<Integer> queue = new DynamicLoopQueue<>(3);
        Scanner sc = new Scanner(System.in);
        char c;
        boolean loop = true;
        while (loop) {
            System.out.println("s(toString):輸出隊列");
            System.out.println("e(exit):退出程序");
            System.out.println("a(add):添加數據到隊列");
            System.out.println("p(poll):從隊列取出數據");
            System.out.println("h(getHead):查看隊列頭的數據");
            System.out.println("n(isEmpty):是否隊空");
            System.out.println("f(isFull):是否隊滿");
            c = sc.next().charAt(0);
            switch (c) {
                case 's':
                    System.out.println("當前隊列:" + queue.toString());
                    break;
                case 'e':
                    sc.close();
                    loop = false;
                    break;
                case 'a':
                    System.out.println("請輸入一個整數");
                    queue.add(sc.nextInt());
                    break;
                case 'p':
                    System.out.printf("出隊元素:%d\n", queue.poll());
                    break;
                case 'h':
                    System.out.printf("隊首元素:%d\n", queue.getHead());
                    break;
                case 'n':
                    System.out.println("隊空:" + queue.isEmpty());
                    break;
                case 'f':
                    System.out.println("隊滿:" + queue.isFull());
                    break;
                default:
                    break;
            }
        }
        System.out.println("程序退出");
    }

}

到此這篇關於Java動態循環隊列是如何實現的的文章就介紹到這瞭,更多相關Java動態循環隊列內容請搜索WalkonNet以前的文章或繼續瀏覽下面的相關文章希望大傢以後多多支持WalkonNet!

推薦閱讀: