鏈隊列是一種基于鏈表實現的隊列結構,它相比于順序隊列而言具有更好的靈活性和空間利用效率。在Java語言中,實現鏈隊列可以通過定義一個節點類和一個隊列類來完成。下面我們將分別詳細介紹鏈隊列的入隊和出隊操作。
入隊操作
public void enqueue(E e){ Node newNode = new Node(e); if(isEmpty()){ front = newNode; rear = newNode; }else{ rear.next = newNode; rear = newNode; } size++; }
鏈隊列的入隊操作相對比較簡單,其本質就是鏈表的尾插操作。首先我們需要創建一個新節點,然后判斷鏈隊列是否為空。如果為空,則直接將新節點作為頭尾節點;如果不為空,將尾節點的next指針指向新節點,然后將尾節點指向新節點。最后,將鏈隊列大小加1即可。
出隊操作
public E dequeue(){ if(isEmpty()) throw new NoSuchElementException(); E element = front.data; front = front.next; size--; if(isEmpty()) rear = null; return element; }
鏈隊列的出隊操作同樣也比較簡單,其本質就是鏈表的頭刪操作。但是要注意,如果鏈隊列為空,則無法進行出隊操作,此時需要拋出NoSuchElementException異常。出隊操作首先需要將頭節點的值賦值給一個變量(即要出隊的數據),然后將頭節點指向原頭節點的后繼節點,并將鏈隊列大小減1。如果出隊后鏈隊列為空,則需要將尾節點置為空,否則會出現異常。