快捷導(dǎo)航

java實現(xiàn)隊列數(shù)據(jù)結(jié)構(gòu)代碼詳解

更新時間：2017年11月15日 15:37:36 作者：顏小雀

這篇文章主要介紹了java實現(xiàn)隊列數(shù)據(jù)結(jié)構(gòu)代碼詳解，簡單介紹了隊列結(jié)構(gòu)以應(yīng)用場景，涉及詳細實現(xiàn)代碼，還是比較不錯的，這里分享給大家，需要的朋友可以參考下。

什么是隊列結(jié)構(gòu)

一種線性結(jié)構(gòu)，具有特殊的運算法則【只能在一端（隊頭）刪除，在另一端（隊尾）插入】。

分類：

順序隊列結(jié)構(gòu)
鏈式隊列結(jié)構(gòu)

基本操作：

入隊列
出隊列　

給出一些應(yīng)用隊列的場景

　　1):當作業(yè)被送到打印機的時候，就可以按到達的順序排起來，因此每一份作業(yè)是隊列的節(jié)點。

　　2):售票口的人買票的順序的按照先來先買的順序售票。

　　3):當所有的終端被占用，由于資源有限，來訪請求需要放在一個隊列中等候。

隊列是先進先出的!　

我們設(shè)置一個叫做LinkQueue<T>的泛型集合類，該類里面有 Node 作為內(nèi)部類（作為節(jié)點用），它包含了泛型元素和下一個node節(jié)點的指向next（Node）。

在Linkqueue的里面設(shè)置隊列頭指針 front和隊列尾指針rear，長度size=0；我們先設(shè)置一個構(gòu)造器LinkQueue()，用來初始化這兩個指針節(jié)點，當然，剛開始初始化的時候這兩個指針僅僅是一個節(jié)點而已，里面的data是空的，我們還讓這兩個指針相等。

//鏈的數(shù)據(jù)結(jié)構(gòu) 
 private class Node{ 
 public T data; 
 public Node next; 
 //無參構(gòu)造函數(shù) 
 public Node(){} 
  
 public Node(T data,Node next){ 
  this.data=data; 
  this.next=next; 
 } 
 } 
 //隊列頭指針 
 private Node front; 
 //隊列尾指針 
 private Node rear;

public LinkQueue(){
	Node n=new Node(null,null);
	n.next=null;
	front=rear=n;
}

當我們向該隊列添加元素的時候，就會生成一個新的節(jié)點，其data就是你要加的元素，（當添加一個節(jié)點時，該節(jié)點就是隊尾指針指向的最后的節(jié)點，一直排在最后），所以隊尾rear.next=newNode(“新創(chuàng)建的節(jié)點”).這是第一個節(jié)點，也是最后一個節(jié)點，所以front.next=newNode.然后我們再讓rear=newNode（不斷更新）。

public void enqueue(T data){ 
 //創(chuàng)建一個節(jié)點 
 Node s=new Node(data,null); 
 //將隊尾指針指向新加入的節(jié)點，將s節(jié)點插入隊尾 
 rear.next=s; 
 rear=s; 
 size++; 
 }

當隊列出隊的時候，還記得我們有一個Node是front.next=newNode 嗎？這就是第一個節(jié)點。先暫且把它叫做p，所以p.next=第二個節(jié)點，這時我們再把front.next=p.next;這樣頭指針就指向了第二個元素(每一次調(diào)用的時候隊列頭指針指會發(fā)生變化)。

public T dequeue(){ 
 if(rear==front){ 
  try { 
  throw new Exception("堆棧為空"); 
  } catch (Exception e) { 
  e.printStackTrace(); 
  } 
  return null; 
 }else{ 
  //暫存隊頭元素 
  Node p=front.next; 
  T x=p.data; 
  //將隊頭元素所在節(jié)點摘鏈 
  front.next=p.next; 
  //判斷出隊列長度是否為1 
  if(p.next==null) 
  rear=front; 
  //刪除節(jié)點 
  p=null; 
  size--; 
  return x; 
 } 
 }

到此為止，隊列的核心操作就完畢了，剩下的比如說size(長度)，isEmpty(是否為空)，就不在說了。(因為太簡單了！)

具體源碼如下：

public class LinkQueue<T> {
	//鏈的數(shù)據(jù)結(jié)構(gòu) 
	private class Node{
		public T data;
		public Node next;
		//無參構(gòu)造函數(shù) 
		public Node(){
		}
		public Node(T data,Node next){
			this.data=data;
			this.next=next;
		}
	}
	//隊列頭指針 
	private Node front;
	//隊列尾指針 
	private Node rear;
	//隊列長度 
	private int size=0;
	public LinkQueue(){
		Node n=new Node(null,null);
		n.next=null;
		front=rear=n;
	}
	/** 
 * 隊列入隊算法 
 * @param data 
 * @author WWX 
 */
	public void enqueue(T data){
		//創(chuàng)建一個節(jié)點 
		Node s=new Node(data,null);
		//將隊尾指針指向新加入的節(jié)點，將s節(jié)點插入隊尾 
		rear.next=s;
		rear=s;
		size++;
	}
	/** 
 * 隊列出隊算法 
 * @return 
 * @author WWX 
 */
	public T dequeue(){
		if(rear==front){
			try {
				throw new Exception("堆棧為空");
			}
			catch (Exception e) {
				e.printStackTrace();
			}
			return null;
		} else{
			//暫存隊頭元素 
			Node p=front.next;
			T x=p.data;
			//將隊頭元素所在節(jié)點摘鏈 
			front.next=p.next;
			//判斷出隊列長度是否為1 
			if(p.next==null) 
			  rear=front;
			//刪除節(jié)點 
			p=null;
			size--;
			return x;
		}
	}
	/** 
 * 隊列長隊 
 * @return 
 * @author WWX 
 */
	public int size(){
		return size;
	}
	/** 
 * 判斷隊列是否為空 
 * @return 
 * @author WWX 
 */
	public Boolean isEmpty(){
		return size==0;
	}
}

另：我曾經(jīng)看過一本JavaScript數(shù)據(jù)結(jié)構(gòu)書，里面講的淺顯易懂，很適合前端搞js開發(fā)的讓人理解的更為深入，在此給予推薦。

《數(shù)據(jù)結(jié)構(gòu)與算法JavaScript描述》

總結(jié)

以上就是本文關(guān)于java實現(xiàn)隊列數(shù)據(jù)結(jié)構(gòu)代碼詳解的全部內(nèi)容，希望對大家有所幫助。感興趣的朋友可以繼續(xù)參閱本站：

Java編程用兩個棧實現(xiàn)隊列代碼分享

java編程實現(xiàn)優(yōu)先隊列的二叉堆代碼分享

java編程隊列數(shù)據(jù)結(jié)構(gòu)代碼示例

如有不足之處，歡迎留言指出。

您可能感興趣的文章: