數據結構（3）：隊列的原理和實現
- 2019 年 10 月 3 日
- 筆記
完整程式碼拉到最底下
一、介紹
隊列顧名思義就像我們生活中排隊一樣，先進先出。
如上圖所示，25、16、5、9依次在隊列中，按照順序拿出的數據也分別是25、26、5、9。
二、實現過程及思路
底層使用數組來實現，實現的功能有插入數據到隊尾、移除隊首數據、查看隊首數據、判斷隊列是否為空、判斷隊列是否存滿。
將隊列的元素存儲在數組的某個區間內，隊列在數組中是連續的，所以使用變數標記隊列在數組中的位置。
1、編寫類及屬性
我們可以使用elements變數標記隊列中元素的數量，使用front變數標記隊首元素在數組的索引，end變數標記隊尾元素在數組中的索引。
public class MyQueue { private Object[] arr;//存放隊列元素的數組 private int elements;//隊列元素數量 private int front;//隊頭元素在數組中的索引 private int end;//隊尾元素在數組中的索引 public MyQueue() { arr = new Object[10]; elements = 0; front = 0; end = -1; } public MyQueue(int maxSize) { arr = new Object[maxSize]; elements = 0; front = 0; end = -1; } }2、隊列是否為空
標記隊列元數量的變數 elements 為 0 即為空
public boolean isEmpty() { return elements == 0; }3、隊列是否已經滿了
隊列元素個數與數組的長度相等即為滿
public boolean isFull() { return elements == arr.length; }4、獲取隊頭元素
獲取數組中索引為 front的元素
public Object peek() { return arr[front]; }5、移除隊首元素
每次都是移除數組中索引為 front 的元素，下一個元素就變成了隊首，即front+1，隊列元素個數elements-1。共有三種情況要考慮，如果隊列已經空了就無須做任何操作，如果已經是最後一個元素，直接將標記位置的變數重置即可，其他情況正常操作。
public Object remove() { if (isEmpty()) { throw new RuntimeException("隊列已經是空的，放心使用吧"); } Object value = arr[front++]; //如果已經是最後一個元素了,將指針重置即可 if (elements == 1) { end = -1; front = 0; elements = 0; } else { elements--; } return value; }6、插入
我們編寫一個持續可用的隊列，所以要考慮到以下情況。
(1)存儲隊列的數組滿了(隊列滿了)，這個好理解，滿了就無法向隊尾加入元素了。
(2)因為隊列在數組中是連續的，如果隊列的元素在數組中最後，需要將元素從隊首到隊尾移到數組中第一位，也就是將後面的位置空出來(參考下圖)。
public void insert(Object value) { //檢測隊列是否已經滿了 if (isFull()) { throw new RuntimeException("隊列內元素已達到設定長度"); } //如果後面沒有空位置，將餘下元素放到數組的頭 if (elements > 1 && end == arr.length - 1) { int i = 0; for (; i < elements; i++, front++) { arr[i] = arr[front]; } front = 0; end = i-1; } //其他情況正常向後添加元素 arr[++end] = value; elements++; }7、測試
public static void main(String[] args) { MyQueue queue = new MyQueue(4); queue.insert(11); queue.insert(12); queue.insert(13); queue.insert(14); queue.remove(); queue.remove(); queue.insert(16); //queue.remove(); //queue.remove(); //queue.insert(19); //queue.insert(20); queue.remove(); queue.remove(); queue.insert(21); queue.insert(22); while (!queue.isEmpty()) { System.out.println(queue.remove()); } }三、完整程式碼
package com.jikedaquan.datastruct; public class MyQueue { private Object[] arr; private int elements;//隊列元素數量 private int front;//隊頭元素在數組中的索引 private int end;//隊尾元素在數組中的索引 public MyQueue() { arr = new Object[10]; elements = 0; front = 0; end = -1; } public MyQueue(int maxSize) { arr = new Object[maxSize]; elements = 0; front = 0; end = -1; } //從隊尾插入 public void insert(Object value) { //檢測隊列是否已經滿了 if (isFull()) { throw new RuntimeException("隊列內元素已達到設定長度"); } //如果後面沒有空位置，將餘下元素放到數組的頭 if (elements > 1 && end == arr.length - 1) { int i = 0; for (; i < elements; i++, front++) { arr[i] = arr[front]; } front = 0; end = i-1; } arr[++end] = value; elements++; } //刪除數據，從隊頭刪除 public Object remove() { if (isEmpty()) { throw new RuntimeException("隊列已經是空的，放心使用吧"); } Object value = arr[front++]; //如果已經是最後一個元素了,將指針重置即可 if (elements == 1) { end = -1; front = 0; elements = 0; } else { elements--; } return value; } //查看數據，從隊頭查看 public Object peek() { return arr[front]; } //判斷是否為空 public boolean isEmpty() { return elements == 0; } public boolean isFull() { return elements == arr.length; } public static void main(String[] args) { MyQueue queue = new MyQueue(4); queue.insert(11); queue.insert(12); queue.insert(13); queue.insert(14); queue.remove(); queue.remove(); queue.insert(16); // queue.remove(); // queue.remove(); // queue.insert(19); // queue.insert(20); queue.remove(); queue.remove(); queue.insert(21); queue.insert(22); while (!queue.isEmpty()) { System.out.println(queue.remove()); } } } 