數據結構與演算法—隊列(搞懂最常用數據結構之一)

• 2019 年 10 月 6 日
• 筆記

前言

• 棧和隊列是一對好兄弟，前面我們介紹過數據結構與演算法—棧詳解，那麼棧的機制相對簡單，後入先出，就像進入一個狹小的山洞，山洞只有一個出口，只能後進先出(在外面的先出去)。而隊列就好比是一個隧道，後面的人跟著前面走，前面人先出去(先入先出)。日常的排隊就是隊列運轉形式的一個描述！
• 所以隊列的核心理念就是：先進先出！
• 隊列的概念：隊列是一種特殊的線性表，特殊之處在於它只允許在表的前端（front）進行刪除操作，而在表的後端（rear）進行插入操作，和棧一樣，隊列是一種操作受限制的線性表。進行插入操作的端稱為隊尾，進行刪除操作的端稱為隊頭。
• 同時，閱讀本偏文章最好先弄懂順序表的基本操作和棧的數據結構！學習效果更佳！

隊列介紹

基本屬性

隊頭front：

• 刪除數據的一端。對於數組，從後面插入更容易，前面插入較困難，所以一般用數組實現的隊列隊頭在前面。(刪除直接index游標前進，不超過隊尾即可)。而對於鏈表。插入刪除在兩頭分別進行那麼頭部(前面)刪除尾部插入是最方便的選擇。

隊尾rear：

• 插入數據的一端，同上，在數組和鏈表中通常均在尾部位置。當然，其實數組和鏈表的front和rear還有點小區別，後面會具體介紹。

enQueue(入隊)：

• 在隊尾rear插入元素

deQueue(出隊)：

• 在對頭front刪除元素

普通隊列

按照上述的介紹，我們很容易知道數組實現的方式。用數組模擬表示隊列。要考慮初始化，插入，問題。

• 初始化：數組的front和rear都指向0.
• 入隊：隊不滿，數組不越界，先隊尾位置傳值，再隊尾下標+1
• 出隊：隊不空，先取隊頭位置元素，在隊頭+1，

但是很容易發現問題，每個空間域只能利用一次。造成空間極度浪費。並且非常容易越界！

循環隊列

針對上述的問題。有個較好的解決方法！就是對已經申請的(數組)記憶體重複利用。這就是我們所說的循環隊列。

而數組實現的循環隊列就是在邏輯上稍作修改。我們假設(約定)數組的最後一位的下一個index是首位。因為我們隊列中只需要front和tail兩個指標。不需要數組的實際地址位置相關數據。和它無關。所以我們就只需要考慮尾部的特殊操作即可。

• 初始化：數組的front和rear都指向0.
• 入隊：隊不滿，先隊尾位置傳值，再rear=(rear + 1) % maxsize;
• 出隊：隊不空，先取隊頭位置元素，front=(front + 1)%maxsize;
• 是否為空：return rear == front;
• 大小：return (rear+maxsize-front)%maxsize;

這裡面有幾個大家需要注意的，就是指標相加如果遇到最後需要轉到頭的話。可以判斷是否到數組末尾位置。也可以直接+1求余。其中maxsize是數組實際大小。

鏈式實現

對於鏈表實現的隊列，要根據先進先出的規則考慮頭和尾的位置

我們知道隊列是先進先出的，對於鏈表，我們能採用單鏈表盡量採用單鏈表，能方便盡量方便，同時還要兼顧效率。

• 方案一 如果隊頭設在鏈表尾，隊尾設在鏈表頭。那麼隊尾進隊插入在鏈表頭部插入沒問題。容易實現，但是如果隊頭刪除在尾部進行，如果不設置尾指針要遍歷到隊尾，但是設置尾指針刪除需要將它指向前驅節點那麼就需要雙向鏈表。都挺麻煩的。
• 方案二但是如果隊頭設在鏈表頭，隊尾設在鏈表尾部，那麼隊尾進隊插入在鏈表尾部插入沒問題(用尾指針可以直接指向next)。容易實現，如果隊頭刪除在頭部進行也很容易，就是我們前面常說的頭節點刪除節點。
• 所以我們最終採取的是方案2的帶頭節點，帶尾指針的單鏈表!

主要操作為：

• 初始化：

public class listQueue<T> {  	static class node<T> {  		T data;// 節點的結果  		node next;// 下一個連接的節點  		public node() {}  		public node(T data) {  			this.data = data;  		}  	}  	node front;//相當於head 帶頭節點的  	node rear;//相當於tail/end  	public listQueue() {  		front=new node<T>();  		rear=front;  	}  

• 入隊：rear.next=va;rear=va;（va為被插入節點）

• 出隊：隊不空，front.next=front.next.next;經典帶頭節點刪除

• 是否為空：return rear == front;
• 大小：節點front遍歷到rear的個數。

具體實現

數組實現

package 隊棧;    public class seqQueue<T> {  	private T data[];// 數組容器  	private int front;// 頭  	private int rear;// 尾  	private int maxsize;// 最大長度    	public seqQueue(int i)// 設置長為i的int 型隊列  	{  		data = (T[]) new Object[i+1];  		front = 0;  		rear = 0;  		maxsize = i+1;  	}    	public int  lenth() {  		return (rear+maxsize-front)%maxsize;  	}  	public boolean isempty() {  		return rear == front;  	}    	public boolean isfull() {  		return (rear + 1) % maxsize == front;  	}    	public void enQueue(T i) throws Exception// 入隊  	{  		if (isfull())  			throw new Exception("已滿");  		else {  			data[rear] = i;  			rear=(rear + 1) % maxsize;  		}  	}    	public T deQueue() throws Exception// 出隊  	{  		if (isempty())  			throw new Exception("已空");  		else {  			T va=data[front];  			front=(front+1)%maxsize;  			return va;  		}  	}    	public String toString()// 輸出隊  	{  		String va="隊頭: ";  		int lenth=lenth();  		for(int i=0;i<lenth;i++)  		{  			va+=data[(front+i)%maxsize]+" ";  		}  		return va;  	}    }  

鏈式實現

package 隊棧;    public class listQueue<T> {  	static class node<T> {  		T data;// 節點的結果  		node next;// 下一個連接的節點  		public node() {}  		public node(T data) {  			this.data = data;  		}  	}  	node front;//相當於head 帶頭節點的  	node rear;//相當於tail/end  	public listQueue() {  		front=new node<T>();  		rear=front;  	}  	public int  lenth() {  		int len=0;  		node team=front;  		while(team!=rear)  		{  			len++;team=team.next;  		}  		return len;  	}  	public boolean isempty() {  		return rear == front;  	}  	public void enQueue(T value) // 入隊.尾部插入  	{  		node va=new node<T>(value);  		rear.next=va;  		rear=va;  	}    	public T deQueue() throws Exception// 出隊  	{  		if (isempty())  			throw new Exception("已空");  		else {  			T va=(T) front.next.data;  			front.next=front.next.next;  			return va;  		}  	}  	public String toString()  	{  		node team=front.next;  		String va="隊頭：";  		while(team!=null)  		{  			va+=team.data+" ";  			team=team.next;  		}  		return va;  	}  }    

測試