快捷導(dǎo)航

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

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

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

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

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

分類：

順序隊(duì)列結(jié)構(gòu)
鏈?zhǔn)疥?duì)列結(jié)構(gòu)

基本操作：

入隊(duì)列
出隊(duì)列　

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

　　1):當(dāng)作業(yè)被送到打印機(jī)的時(shí)候，就可以按到達(dá)的順序排起來(lái)，因此每一份作業(yè)是隊(duì)列的節(jié)點(diǎn)。

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

　　3):當(dāng)所有的終端被占用，由于資源有限，來(lái)訪請(qǐng)求需要放在一個(gè)隊(duì)列中等候。

隊(duì)列是先進(jìn)先出的!　

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

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

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

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

當(dāng)我們向該隊(duì)列添加元素的時(shí)候，就會(huì)生成一個(gè)新的節(jié)點(diǎn)，其data就是你要加的元素，（當(dāng)添加一個(gè)節(jié)點(diǎn)時(shí)，該節(jié)點(diǎn)就是隊(duì)尾指針指向的最后的節(jié)點(diǎn)，一直排在最后），所以隊(duì)尾rear.next=newNode(“新創(chuàng)建的節(jié)點(diǎn)”).這是第一個(gè)節(jié)點(diǎn)，也是最后一個(gè)節(jié)點(diǎn)，所以front.next=newNode.然后我們?cè)僮宺ear=newNode（不斷更新）。

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

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

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

到此為止，隊(duì)列的核心操作就完畢了，剩下的比如說(shuō)size(長(zhǎng)度)，isEmpty(是否為空)，就不在說(shuō)了。(因?yàn)樘?jiǎn)單了！)

具體源碼如下：

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

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

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

總結(jié)

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

Java編程用兩個(gè)棧實(shí)現(xiàn)隊(duì)列代碼分享

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

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

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

您可能感興趣的文章: