天天看點
傳回

1.2資料結構學習-隊列隊列

1.2資料結構學習-隊列

  • 隊列
    • 非環形隊列
      • 數組實作非環形隊列思路
      • 數組實作非環形隊列DEMO
    • 非環形隊列
      • 數組實作非環形隊列思路
      • 數組實作非環形隊列DEMO

隊列 

1.描述：一種有序清單，可用數組或連結清單進行實作
2.存取原則：先進先出
3.種類：
	1).非環形隊列：隊列内不重複使用已取出資料的位置進行再次存儲
	2).環形隊列：隊列内已取出資料的位置可繼續進行重複存儲

非環形隊列

數組實作非環形隊列思路 

1.設定maxSize為隊列長度，則設定數組 array=Object[maxSize]
   2.為保持先進先出原則，則需記錄[預存入下标]及[預讀取下标]，設預存入下标end，預讀取下标front,初始值front=end=0(未存入)
   3.隊列新增下一個元素則[預存入下标]end++
   4.隊列讀取下一個元素則[預讀取下标]front++
   5.其中有效元素個數size=end-front
       如：存入5個元素，end=5,取出3個元素，front=3，則(size=5-3)==end-front
   6.僅當end-front==0時隊列為空,end==maxSize隊列為滿

數組實作非環形隊列DEMO 

/**
 * @Auther: lxh
 * @Date: 2019/7/16/016 17:20
 * @Description: 數組實作隊列
 */
public class ArrayQueue
{
    /**
     * 隊列内部存儲數組
     */
    private int[] arr;
    /**
     * 隊列最大存儲長度
     */
    private int maxSize;
    /**
     * 隊列有效元素個數
     */
    private int size;
    /**
     * 隊列目前預讀取下标
     */
    private int front;
    /**
     * 隊列目前預存入下标
     */
    private int end;

    public ArrayQueue(int maxSize)
    {
        this.maxSize = maxSize;
        arr = new int[maxSize];
        size = 0;
        front = 0;
        end = 0;
    }

    /**
     * @param value 存入值
     * @desc :隊列插入資料
     * 1.在數組對應預存入下标位置指派
     * 2.有效元素數量+1
     * 3.預存入下标+1
     * @author lxh
     * @date 2021/5/20 0020 1:32
     **/
    public void insert(int value)
    {
        if (isFull())
        {
            System.out.println("隊列滿，不能加入資料~");
            return;
        }
        size++;
        arr[end++] = value;
    }

    /**
     * @return : int 所取出資料
     * 1.讀取數組對應預讀取下标位置元素
     * 2.有效元素數量-1
     * 3.讀取下标+1
     * @desc :隊列取出資料
     * @author lxh
     * @date 2021/5/20 0020 1:32
     **/
    public int remove()
    {
        // 判斷隊列是否空
        if (isEmpty())
        {
            System.out.println("隊列空，不能取資料~");
            throw new RuntimeException("隊列空，不能取資料");
        }
        size--;
        // front後移
        return arr[front++];
    }

    /**
     * @return boolean
     * @desc :判斷隊列是否為空
     * 1.僅當存儲下标==讀取下标時,說明存儲的均已讀取,此時為空
     * @author lxh
     * @date 2021/5/20 0020 1:35
     **/
    public boolean isEmpty()
    {
        return (front == end);
    }

    /**
     * @return boolean
     * @desc :判斷隊列是否已到達最大長度
     * 1.僅當存儲下标==隊列内數組最大下标時,此時隊列已滿
     * 1.僅當存儲下标-讀取下标時=隊列最大長度時,說明可讀取的有效元素數量已達到最大長度,此時隊列已滿
     * @author lxh
     * @date 2021/5/20 0020 1:35
     **/
    public boolean isFull()
    {
        return (end == maxSize);
    }

    public static void main(String[] args)
    {
        ArrayQueue arrayQueue = new ArrayQueue(5);
        System.out.println("---------------------");
        System.out.println("隊列是否為空:" + arrayQueue.isEmpty());

        System.out.println("---------------------");
        System.out.println("開始加入資料:");
        int i = 0;
        while (!arrayQueue.isFull())
        {
            System.out.println("加入資料: " + i);
            arrayQueue.insert(i);
            i++;
        }

        System.out.println("---------------------");
        System.out.println("隊列是否已滿：" + arrayQueue.isFull());

        System.out.println("---------------------");
        System.out.println("測試隊列已滿是否可繼續加入元素:");
        arrayQueue.insert(i + 1);

        System.out.println("---------------------");
        System.out.println("開始取出資料:");
        while (!arrayQueue.isEmpty())
        {
            System.out.println("取出資料: " + arrayQueue.remove());
        }


        System.out.println("---------------------");
        System.out.println("隊列是否為空:" + arrayQueue.isEmpty());

        System.out.println("---------------------");
        System.out.println("測試隊列已空是否可繼續取出元素:");
        System.out.println(arrayQueue.remove());
        System.out.println("---------------------");
    }
}

結果

---------------------
隊列是否為空:true
---------------------
開始加入資料:
加入資料: 0
加入資料: 1
加入資料: 2
加入資料: 3
加入資料: 4
---------------------
隊列是否已滿：true
---------------------
測試隊列已滿是否可繼續加入元素:
隊列滿，不能加入資料~
---------------------
開始取出資料:
取出資料: 0
取出資料: 1
取出資料: 2
取出資料: 3
取出資料: 4
---------------------
隊列是否為空:true
---------------------
測試隊列已空是否可繼續取出元素:
隊列空，不能取資料~
Exception in thread "main" java.lang.RuntimeException: 隊列空，不能取資料
	at com.lxh.structure.queue.ArrayQueue.remove(ArrayQueue.java:75)
	at com.lxh.structure.queue.ArrayQueue.main(ArrayQueue.java:143)

非環形隊列

數組實作非環形隊列思路 

1.設定maxSize為隊列長度，則設定數組 array=Object[maxSize]
2.為保持先進先出原則，則需記錄[預存入下标]及[預讀取下标]，設預存入下标rear，預讀取下标設預存入下标front,初始值front=rear=0(未存入)
3.隊列新增下一個元素則存入下标rear++,考慮數組已滿時會循環重新從數組首進行覆寫存儲（已讀取部分），則rear須對maxSize取餘,即rear=(++rear)%maxSize
4.隊列讀取下一個元素則讀取下标front++,考慮會已讀取部分會重新存儲，讀取到數組尾部時須從數組首繼續讀取,，則front須對maxSize取餘，即front=(++front)%maxSize
5.其中有效元素個數size=(rear-front+maxSize)%maxSize
       如：maxSize=5,存入4個元素，rear=4,取出3個元素，front=3，則(size=4-3)==(rear-front+maxSize)%maxSize
       如：maxSize=5,存入7個元素，rear=2,取出3個元素，front=3，則(size=7-3)==(rear-front+maxSize)%maxSize
6.避免rear=front時，難以判斷是已存儲滿或存儲為空，約定空出一個位置
7.僅當rear-front==0時隊列為空
  僅當rear+1==front時隊列為滿

數組實作非環形隊列DEMO 

/**
 * @author: 李旭輝
 * @Date: 2019/8/5 0005 22:26
 * @description： 環形隊列
 */
public class CircleArrayQueue
{
    /**
     * 隊列内部存儲數組
     */
    private int[] arr;
    /**
     * 隊列最大存儲長度
     */
    private int maxSize;
    /**
     * 隊列目前預讀取下标
     */
    private int front;
    /**
     * 隊列目前預存入下标
     */
    private int rear;

    public CircleArrayQueue(int maxSize)
    {
        this.maxSize = maxSize;
        this.arr = new int[maxSize];
    }

    /**
     * @return boolean
     * @desc :判斷隊列是否存儲滿
     * 1.僅當預存儲下标已重複從數組頭開始存儲，且預存儲下标距離預讀取下标剩餘1時,此時隊列已滿
     * @author lxh
     * @date 2021/5/20 0020 1:35
     **/
    public boolean isFull()
    {
        return (rear + 1) % maxSize == front;
    }

    /**
     * @return boolean
     * @desc :判斷隊列是否為空
     * 1.僅當存儲下标==讀取下标時,說明存儲的均已讀取,此時為空
     * @author lxh
     * @date 2021/5/20 0020 1:35
     **/
    public boolean isEmpty()
    {
        return rear == front;
    }

    /**
     * @param value 存入值
     * @desc :隊列插入資料
     * 1.存入下标+1
     * 2.在數組對應預存入下标位置指派
     * 2.有效元素數量+1
     * @author lxh
     * @date 2021/5/20 0020 1:32
     **/
    public void insert(int value)
    {
        if (isFull())
        {
            System.out.println("隊列滿，不能加入資料~");
            return;
        }
        arr[rear] = value;
        rear = (rear + 1) % maxSize;
    }

    /**
     * @return : int 所取出資料
     * 1.讀取數組對應預讀取下标位置元素
     * 2.有效元素數量-1
     * 3.讀取下标+1
     * @desc :隊列取出資料
     * @author lxh
     * @date 2021/5/20 0020 1:32
     **/
    public int getQueue()
    {
        if (isEmpty())
        {
            throw new RuntimeException("隊列空，不能取資料");
        }
        int value = arr[front];
        front = (front + 1) % maxSize;
        return value;
    }

    /**
     * @desc :顯示隊列的所有資料
     * @author lxh
     * @date 2021/5/20 0020 1:32
     **/
    public void showQueue()
    {
        if (isEmpty())
        {
            System.out.println("隊列空的，沒有資料~~");
            return;
        }
        for (int i = front; i < front + size(); i++)
        {
            System.out.printf("arr[%d]=%d\n", i % maxSize, arr[i % maxSize]);
        }
    }

    /**
     * @return : int 有效資料個數
     * @desc :求出目前隊列有效資料的個數
     * @author lxh
     * @date 2021/5/20 0020 1:32
     **/
    public int size()
    {
        return (rear + maxSize - front) % maxSize;
    }


    public static void main(String[] args)
    {
        CircleArrayQueue circleArrayQueue = new CircleArrayQueue(5);
        System.out.println("---------------------");
        System.out.println("隊列是否為空:" + circleArrayQueue.isEmpty());
        System.out.println("---------------------");
        System.out.println("開始加入資料:");
        int i = 0;
        while (!circleArrayQueue.isFull())
        {
            System.out.println("加入資料: " + i);
            circleArrayQueue.insert(i);
            i++;
        }
        System.out.println("---------------------");
        System.out.println("隊列是否已滿：" + circleArrayQueue.isFull());

        System.out.println("---------------------");
        System.out.println("此時隊列元素明細為:");
        circleArrayQueue.showQueue();
        System.out.println("---------------------");
        System.out.println("測試隊列已滿是否可繼續加入元素:");
        circleArrayQueue.insert(i + 1);

        System.out.println("---------------------");
        System.out.println("開始取出資料:");
        while (!circleArrayQueue.isEmpty())
        {
            System.out.println("取出資料: " + circleArrayQueue.getQueue());
        }
        System.out.println("---------------------");
        System.out.println("隊列是否為空:" + circleArrayQueue.isEmpty());

        System.out.println("---------------------");
        System.out.println("測試隊列已空是否可繼續取出元素:");
        System.out.println(circleArrayQueue.getQueue());
        System.out.println("---------------------");

    }
}

結果

---------------------
隊列是否為空:true
---------------------
開始加入資料:
加入資料: 0
加入資料: 1
加入資料: 2
加入資料: 3
---------------------
隊列是否已滿：true
---------------------
此時隊列元素明細為:
arr[0]=0
arr[1]=1
arr[2]=2
arr[3]=3
---------------------
測試隊列已滿是否可繼續加入元素:
隊列滿，不能加入資料~
---------------------
開始取出資料:
取出資料: 0
取出資料: 1
取出資料: 2
取出資料: 3
---------------------
隊列是否為空:true
---------------------
測試隊列已空是否可繼續取出元素:
Exception in thread "main" java.lang.RuntimeException: 隊列空，不能取資料
	at com.lxh.structure.queue.CircleArrayQueue.getQueue(CircleArrayQueue.java:90)
	at com.lxh.structure.queue.CircleArrayQueue.main(CircleArrayQueue.java:167)
資料結構筆記 資料結構
上一篇: 資料結構學習記錄（四）------循環隊列前言循環隊列的參數以及各個參數的含義初始化循環隊列判斷循環隊列是否已滿入隊周遊判斷循環隊列是否為空出隊整體代碼實作參考資料
下一篇: 中企搬入首台光刻機，美日荷聯盟始料未及，比爾蓋茨說的很對

繼續閱讀