- 今天要學習的隊列,也是一種線性結構,他包括兩類
- 順序隊列:即使用一組位址連續的記憶體單元依次儲存隊列中的資料
- 鍊式隊列:即使用連結清單形式儲存隊列中各元素的值
- 隊列用圖來表示就是這樣的
- 從圖中可以看出,隊列允許在兩端進行操作,一段進行添加操作,稱為隊尾,以便進行删除操作稱為隊頭,他遵循了先進先出FIFO(first in first out)的規則,那這是什麼意思呢?拿生活中的例子就是排隊,先來的拍前面,前面的先接受服務
- 從上面也可以看出來,隊列的基本操作隻有兩種
- 入隊:就是将元素添加到隊尾
- 出隊:就是将隊頭的元素移出
- 那麼我們來看的一下隊列的入隊出隊流程
- 注意:上圖的添加順序是按照數字的大小順序添加的,而非從右到左添加的:即添加順序為0>1>2>3>4>5>6,而不是類似壓入棧的順序:6>5>4>3>2>1>0
- 如上就反映出來一個問題:随着出隊和入隊的操作,tail指針一直在往後移,也就導緻了整個隊列在"假變小",因為入隊隻能在一端進行,是以tail就一直往後移,導緻了前面的出隊後的位置不能再次利用,那麼我們應該怎麼去解決這個問題
- 我的想法是:head從0開始計算,數組的Max_Size是最大下标加一的值,是以當head==Max_Size的時候,就代表了head指針已經到數組外了,那麼就代表數組内元素全部取完了,是一個空隊列,在這個時候,将head和tail都恢複到空隊列狀态
隊列結構順序隊列鍊式隊列 - 如上圖,當tail到達末尾,而head之前有一個空位置,這個現象造成的原因就是先将隊列插滿,然後取出一個,當遇到這種情況下,在執行插入元素的時候,是插入不進去的,因為tail到達末尾了,是以我們将head到tail之間的元素移動到最前方位置,然後更改head和tail的指針即可,這時候後面就會空出一個位置讓新元素插入進來,如下圖
- 知道了基本的入隊出隊規律,下面就是代碼實作
順序隊列
import java.util.Arrays;
public class MyQueue<T> {
//頭指針
private int head;
//尾指針
private int tail;
//預設大小
private final int MAX_SIZE ;
//存放資料的數組
private Object[] elementData;
public MyQueue() {
this.MAX_SIZE = 5;
elementData = new Object[MAX_SIZE];
}
public MyQueue(int init_size) {
this.MAX_SIZE = init_size;
elementData = new Object[MAX_SIZE];
}
//添加tail
public void put(T element){
//代表空隊列
if (head == MAX_SIZE){
//将頭指針和尾指針都恢複到空隊列狀态
tail = 0;
head = 0;
}
//代表tail已經添加到隊列末尾了
if (tail == MAX_SIZE){
//不等于0就說明head前面已經有取出的元素了,代表有可用位置
if (head != 0){
//臨時數組
Object[] temp = new Object[MAX_SIZE];
//将元素拷貝到臨時數組的開始位置,排除原來數組之前的可以空位置
System.arraycopy(elementData,head,temp,0,tail - head);
//拷貝完成指派
elementData = temp;
//tail就是指向數組有效元素的最後一個下标
tail = MAX_SIZE - head;
//既然已經将數組元素移動到最開始了,那麼head肯定是指向最開始的位置了
head = 0;
//然後将本次資料存放在數組最後一個元素中
elementData[tail] = element;
//tail後移
tail ++;
return;
}
//代表head=0并且tail等于最大值,那麼就說明存滿了
throw new RuntimeException("隊列已滿");
}
//正常存放
elementData[tail] = element;
tail ++;
}
//拿出head
public T get(){
//空的
if (head >= tail){
return null;
}
//取出頭元素
T element = (T) elementData[head];
//釋放頭元素位置空間
elementData[head] = null;
//head後移
head ++;
//傳回資料
return element;
}
@Override
public String toString() {
return Arrays.toString(elementData) + head + " : " + tail;
}
} - 測試
public static void main(String[] args) { MyQueue<Integer> queue = new MyQueue<>(); queue.put(1); System.out.println(queue); queue.put(2); System.out.println(queue); queue.put(3); System.out.println(queue); queue.put(4); System.out.println(queue); queue.put(5); System.out.println(queue); queue.get(); System.out.println(queue); queue.get(); System.out.println(queue); queue.get(); System.out.println(queue); queue.get(); System.out.println(queue); queue.get(); System.out.println(queue); queue.put(6); System.out.println(queue); queue.put(7); System.out.println(queue); queue.put(8); System.out.println(queue); queue.put(9); System.out.println(queue); queue.put(10); System.out.println(queue); queue.get(); System.out.println(queue); queue.get(); System.out.println(queue); queue.get(); System.out.println(queue); System.out.println("-----------------------"); queue.put(11); System.out.println(queue); queue.put(12); System.out.println(queue); queue.put(13); System.out.println(queue); } - 結果
[1, null, null, null, null]0 : 1 [1, 2, null, null, null]0 : 2 [1, 2, 3, null, null]0 : 3 [1, 2, 3, 4, null]0 : 4 [1, 2, 3, 4, 5]0 : 5 [null, 2, 3, 4, 5]1 : 5 [null, null, 3, 4, 5]2 : 5 [null, null, null, 4, 5]3 : 5 [null, null, null, null, 5]4 : 5 [null, null, null, null, null]5 : 5 [6, null, null, null, null]0 : 1 恢複操作 [6, 7, null, null, null]0 : 2 [6, 7, 8, null, null]0 : 3 [6, 7, 8, 9, null]0 : 4 [6, 7, 8, 9, 10]0 : 5 [null, 7, 8, 9, 10]1 : 5 [null, null, 8, 9, 10]2 : 5 [null, null, null, 9, 10]3 : 5 ----------------------- [9, 10, 11, null, null]0 : 3 遷移操作 [9, 10, 11, 12, null]0 : 4 [9, 10, 11, 12, 13]0 : 5
鍊式隊列
- 鍊式結構就不存在可用空位置了,隻要取出直接改變引用即可,同樣需要頭指針和尾指針,下面是代碼實作
public class MyLinkedQueue<T> { private int size; private Node<T> head; private Node<T> tail; private class Node<T>{ private T element ; private Node<T> next; public Node(T element, Node<T> next) { this.element = element; this.next = next; } @Override public String toString() { return String.valueOf(element); } } public MyLinkedQueue() { head = new Node<>(null,null); tail = new Node<>(null,null); } //入隊 public void put(T element){ //代表空連結清單 if (head.next == null){ head.next = new Node<>(element,null); tail = head.next; return; } Node<T> node = new Node<>(element,null); tail.next = node; tail = tail.next; size ++; } //出隊 public T get(){ if (head.next == null) { return null; } Node<T> next = head.next; head = head.next; size --; return (T) next; } public int getSize() { return size; } @Override public String toString() { StringBuilder builder = new StringBuilder(); builder.append("["); for (Node<T> node = head.next ; node != null ; node = node.next){ builder.append(node.toString()+" "); } return builder.toString(); } } -
public static void main(String[] args) { MyLinkedQueue<Integer> queue = new MyLinkedQueue<>(); queue.put(1); queue.put(2); queue.put(3); queue.put(4); System.out.println(queue); queue.get(); System.out.println(queue); queue.get(); System.out.println(queue); queue.get(); System.out.println(queue); queue.get(); System.out.println(queue); queue.get(); System.out.println(queue); queue.put(5); System.out.println(queue); queue.put(6); System.out.println(queue); System.out.println(queue.get()); } -
[1 2 3 4 [2 3 4 [3 4 [4 [ [ [5 [5 6 5