什么是隊列?

隊列是一個有序列表,可以用數(shù)組或鏈表實現(xiàn)
遵循先入先出的(First in First Out)原則。即:先存入隊列的數(shù)據(jù)，要先取出。后存入的要后取出
當(dāng)隊列中插入元素后,此元素可以被讀取
當(dāng)隊列中元素被取出后,此元素就會從隊列中移出

隊列初始狀態(tài)圖解

image.png

從上圖可以看出數(shù)組隊列中包含元素:
????1. 隊列頭指針,用來記錄當(dāng)前隊列可讀取的元素位置
????2. 隊列尾指針,用來記錄當(dāng)前隊列可以寫入的元素位置
????3. 隊列的容量大小(數(shù)組容量)
????4. 隊列中的數(shù)組
????5. 隊列中可讀取的元素數(shù)量

隊列應(yīng)該有那些方法?

一個隊列應(yīng)該需要那些操作?
????1. 將元素插入隊列方法 enQueue(item) 操作tail尾指針寫入元素數(shù)據(jù)
????2. 獲取隊列元素方法 E deQeueu() 操作front頭指針從隊列中獲取元素數(shù)據(jù)
????3. 查看隊列當(dāng)前頭指針的元素 E showFront()
????4. 獲取隊列中的元素數(shù)量 int getSize()
????5. 判斷隊列是否為空 boolean isEmpty()

隊列實戰(zhàn)案例一:數(shù)組實現(xiàn)隊列

數(shù)組實現(xiàn)隊列思路分析:

1. 定義隊列數(shù)組,定義頭指針與尾指針和size
2. 初始化隊列數(shù)組,頭指針,尾指針,通過構(gòu)造函數(shù)完成
3. 編寫enQueue(item)添加元素操作
   添加元素需要判斷隊列是否已經(jīng)滿,沒有滿才可以插入元素
   如何判斷隊列滿了?
   如果tail==capacity表示隊列滿了
   如何隊列滿了應(yīng)該怎么辦?
   擴容,第一個案例我們先不使用擴容來操作,后面再進行擴容操作
4. 編寫deQueue()取出元素操作
   取出元素操作需要判斷列表是否為空,為空表示沒有數(shù)據(jù)
5. 編寫getSize()獲取元素數(shù)量操作
6. 編寫判斷隊列是否為空的操作
   如何判斷隊列中沒有元素?
   如果頭指針與尾指針相等,則表示沒有元素,所以tail==front就表示隊列為空

• 編寫隊列接口

/**
 * @author 凡人靜水
 * 注釋: 此接口定義隊列的接口方法
 */
public interface Queue {
    //添加元素到隊列
    int enQueue(int e);

    //從隊列中取出元素
    int deQeueu();

    //查看隊列頭元素
    int showFront();

    //查看有多少元素可讀
    int getSize();

    //判斷隊列是否為空
    boolean isEmpty();
}

• 編寫隊列實現(xiàn)

/**
 * @author 凡人靜水
 * 注釋: 數(shù)組實現(xiàn)隊列
 */
public class IntArrayQueue implements Queue {

    //1.定義隊列數(shù)組,定義頭指針與尾指針和size
    private int[] arr;
    private int capacity;
    private int front;
    private int tail;
    private int size;

    //2.初始化隊列數(shù)組,頭指針,尾指針,通過構(gòu)造函數(shù)完成
    public IntArrayQueue(int capacity) {
        this.arr = new int[capacity];
        this.capacity = capacity;
        this.front = 0;
        this.tail = 0;
        this.size = 0;
    }

    public IntArrayQueue() {
        //默認創(chuàng)建大小為5的數(shù)組
        this(5);
    }


    //3.編寫enQueue(item)添加元素操作
    public void enQueue(int e) {
        //添加元素需要判斷隊列是否已經(jīng)滿,沒有滿才可以插入元素
        if (tail == capacity) {
            throw new RuntimeException("隊列滿了...請擴容");
        }
        //添加元素,只需要改變尾指針即可
        arr[tail] = e;
        //插入元素后,尾指針需要向前移動一位,準備好下次元素插入的位置
        tail++;
        //插入元素時需要給size++,表示隊列中元素個數(shù)
        size++;
    }

    //4.編寫deQueue()取出元素操作
    public int deQeueu() {
        //取出元素操作需要判斷列表是否為空,為空表示沒有數(shù)據(jù)
        if (isEmpty()) {
            throw new RuntimeException("隊列中沒有元素...");
        }

        int result = arr[front];
        //取出數(shù)據(jù)通過頭指針,取出后移動到下一個讀取的位置
        front++;
        //取出元素時需要給size--,表示隊列中元素個數(shù)
        size--;
        return result;
    }

    //7.查看隊列的頭部
    public int showFront() {
        if (isEmpty())
            System.out.println("隊列中沒有元素....");
        return arr[front];
    }

    //5.編寫getSize()獲取元素數(shù)量操作
    public int getSize() {
        return size;
    }

    //6.編寫判斷隊列是否為空的操作
    public boolean isEmpty() {
        return tail == front;
    }


    @Override
    public String toString() {
        StringBuilder res = new StringBuilder();
        res.append(String.format("Array: size = %d ,capacity=%d , front=%d , tail=%d\n", size, capacity, front, tail));
        res.append("[");
        for (int i = front; i < tail; i++) {
            res.append(arr[i]);
            if (i != (tail - 1) ){
                res.append(",");
            }
        }
        res.append("]");
        return res.toString();
    }
}

• 編寫測試

 public static void main(String[] args) {
        IntArrayQueue queue = new IntArrayQueue(10);
        System.out.println("添加數(shù)據(jù):");
        for (int i = 0; i < 3; i++) {
            try {
                queue.enQueue(i);
            } catch (Exception e) {
                break;
            }
            System.out.println(queue);
            System.out.println("----------------------------------");
        }
        int result = queue.deQeueu();
        System.err.println("取出數(shù)據(jù):" + result);
        System.err.println(queue);
        result = queue.deQeueu();
        System.err.println("取出數(shù)據(jù):" + result);
        System.err.println(queue);
    }

• 測試結(jié)果

添加數(shù)據(jù):
Array: size = 1 ,capacity=10 , front=0 , tail=1
[0]
----------------------------------
Array: size = 2 ,capacity=10 , front=0 , tail=2
[0,1]
----------------------------------
Array: size = 3 ,capacity=10 , front=0 , tail=3
[0,1,2]
----------------------------------
取出數(shù)據(jù):0
Array: size = 2 ,capacity=10 , front=1 , tail=3
[1,2]
取出數(shù)據(jù):1
Array: size = 1 ,capacity=10 , front=2 , tail=3
[2]

圖解隊列執(zhí)行流程

第一次添加元素

image.png

第二次添加元素

image.png

image.png

第一次取出元素

image.png

image.png

數(shù)組隊列的問題

通過上面的測試結(jié)果,發(fā)現(xiàn)以下問題:

當(dāng)取出數(shù)據(jù)后,發(fā)現(xiàn)front的值為2,此時,隊列的前兩個空間沒有被使用,而之后插入也都不會插入到這兩個空間中,所以被浪費掉了!
結(jié)論:只要取出數(shù)據(jù)后,空間就沒辦法再用了,只能通過擴容來維護新的數(shù)組,這肯定不是好的解決方案
解決方案:通過環(huán)形(循環(huán))隊列來解決上面的問題,下一章我們看看環(huán)形隊列如何實現(xiàn),及其實現(xiàn)原理

搜索公眾號,查看更多專題文章:javastu