【数据结构】之队列的java实现（二）详解编程语言

在上一篇博文中通过java实现了队列的连续存储，下面来讨论队列的链式存储，即链队列。

链队列的定义：

队列的链式存储结构简称为链队列。它是限制仅在表头删除和表尾插入的单链表。

链队列的数据存储形式：

 链队列基本运算的实现：

package study_02.datastructure.queue; 
 
 
/** 
 * 链队列 
 * @author WWX 
 */ 
public class LinkQueue<T> { 
	 
	//链的数据结构 
	private class Node{ 
		public  T data; 
		public  Node next; 
		//无参构造函数 
		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){ 
		//创建一个节点 
		Node s=new Node(data,null); 
		//将队尾指针指向新加入的节点，将s节点插入队尾 
		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; 
			//将队头元素所在节点摘链 
			front.next=p.next; 
			//判断出队列长度是否为1 
			if(p.next==null) 
				rear=front; 
			//删除节点 
			p=null; 
			size--; 
			return  x; 
		} 
	} 
	 
	/** 
	 * 队列长队 
	 * @return 
	 * @author WWX 
	 */ 
	public int size(){ 
		return size; 
	} 
	 
	/** 
	 * 判断队列是否为空 
	 * @return 
	 * @author WWX 
	 */ 
	public  boolean isEmpty(){ 
		return  size==0; 
		 
	} 
	 
	 
	public String toString() { 
		if(isEmpty()){ 
			return "[]"; 
		}else{ 
			StringBuilder sb = new StringBuilder("["); 
			for(Node current=front.next;current!=null;current=current.next){ 
				sb.append(current.data.toString() + ", "); 
			} 
			int len = sb.length(); 
			return sb.delete(len - 2, len).append("]").toString(); 
		} 
	} 
	 
	//测试 
	public static void main(String[] args) { 
		LinkQueue<Integer> queue=new LinkQueue<Integer>(); 
		queue.enqueue(1); 
		queue.enqueue(2); 
		queue.enqueue(3); 
		queue.enqueue(4); 
		queue.enqueue(5); 
		queue.enqueue(6); 
		System.out.println(queue); 
		System.out.println("出队："+queue.dequeue()); 
		System.out.println("队列长度="+queue.size()); 
		System.out.println(queue); 
		System.out.println("出队："+queue.dequeue()); 
		System.out.println("队列长度="+queue.size()); 
		System.out.println(queue); 
		System.out.println("出队："+queue.dequeue()); 
		System.out.println("队列长度="+queue.size()); 
		System.out.println(queue); 
	} 
} 

输出结果：

[1, 2, 3, 4, 5, 6]
出队：1
队列长度=5
[2, 3, 4, 5, 6]
出队：2
队列长度=4
[3, 4, 5, 6]
出队：3
队列长度=3
[4, 5, 6]