數據結構—隊列及簡單實現有界隊列
- 2020 年 4 月 6 日
- 筆記
隊列也是一種特殊的線性表，它只允許在兩端進行操作，插入或者取出，不允許操作中間的數據。比如只允許在對頭出隊，隊尾入隊。這樣就具有先進先出的特性（first in first out-FIFO）。就像排隊買東西一樣，不允許插隊，先排先買。
隊列分為單向隊列（有序隊列），就是上面所說的排隊模型，先進先出的操作，只允許一邊進，另一邊出，比如Java中的Queue。另外一種就是雙端隊列，兩端都可以進行進出操作。比如java中的Deque。
既然隊列也是線性表的一種，那麼實現隊列，就可以用數組或者鏈表來實現。
如果再細分一點的話，可以看著這倆介面的實現，簡單列舉幾個：
PriorityQueue：數組實現的有序隊列，可以傳入一個比較器Comparator，實現隊列中元素的順序。。
ArrayDeque：數組實現的雙端隊列
LinkedList：用鏈表實現的雙端隊列
Juc並發包下面：
ArrayBlockingQueue：數組實現的阻塞隊列
PriorityBlockingQueue：帶優先順序的阻塞隊列
LinkedBlockingQueue：鏈表實現的阻塞隊列
可以看出大佬們的命名是很規範的，從類名直接可以看出來這隊列的特性以及用什麼數據結構實現的。
簡單用數組實現一個有界隊列
1.初始化一個數組，這個是頭尾都是指向的0
2.插入三個元素，尾移動三位，指向了3
3.取出一個元素，頭移動一位指向了1
我們會發現頭指針走過的數組元素其實是空出來了的（index = 0）。假設尾指針走到最後了，但是因為我們有取出元素，前面有空位，所以按理來說，我們還可以繼續加入元素進去，但是這個時候怎麼指針怎麼回去呢？可以重新創建一個數組繼續開始，這樣的話會重新開闢記憶體空間，而且還需要將現有的數據複製到新的數組中去。如果我們只想讓這個隊列保持初始化大小，沒有擴容操作，創建一個新的數組去繼續放，從空間和時間複雜度來說都不合適了。這個時候我們可以通過取模操作，讓指針回去，從頭開始，既不用開闢新空間，也不用移動數據。這樣的話就需要考慮空隊列和滿隊這兩個狀態的判斷。如果滿了就無法插入，新數據直接丟棄，按如上邏輯實現一個簡單隊列。
package com.nijunyang.algorithm.queue; /** * Description: * Created by nijunyang on 2020/4/4 21:44 */ public class MyQueue<E> { private static final int DEFAULT_SIZE = 10; private Object[] elements; private int headIndex; private int tailIndex; private int capacity; //從容量 private int size; //已放元素個數 public MyQueue() { this(DEFAULT_SIZE); } public MyQueue(int capacity) { this.elements = new Object[capacity]; this.capacity = capacity; } public void push(E e){ if (isFull()) { //插入先判斷是否滿 return; } elements[tailIndex] = e; size++; tailIndex = (tailIndex + 1) % capacity; //取模實現循環的操作 } public E pop(){ if(isEmpty()) { //取元素先判空 return null; } E e = (E) elements[headIndex]; headIndex = (headIndex + 1) % capacity; //取模實現循環的操作 size--; return e; } public boolean isEmpty(){ return this.size == 0; } public int size(){ return this.size; } public int getCapacity(){ return this.capacity; } public boolean isFull(){ return this.size == this.capacity; } public static void main(String[] args) { MyQueue<Integer> myQueue = new MyQueue(3); myQueue.push(1); System.out.println(myQueue.size()); myQueue.push(2); myQueue.push(3); System.out.println(myQueue.pop()); System.out.println(myQueue.size()); myQueue.push(4); myQueue.push(5); System.out.println(myQueue.size()); } }
