队列（三） --- 队列的链式存储

类似使用链式存储结构保存线性表， 这里也可以使用链式结构存储队列中的各元素，我们可以称置为链队列。

主要就是插入队列和移除队列，可参看一下（制作粗糙，请见谅）：（依次是原队列、插入元素、删除数据后的形式）

参考代码：

public class LinkQueue<T> {

	private class Node{
		//保存节点的数据
		private T data;
		//指向下一个节点的引用
		private Node next;
		public Node(){

		}
		public Node(T data, Node next){
			this.data = data;
			this.next = next;
		}
	}
	//记录队列中已包含的节点数
	private int size;
	//保存节点的头节点和尾节点
	private Node front;
	private Node rear;

	//根据默认的长度构建一个顺序队列
	public LinkQueue(){
		//空队列
		front = null;
		rear = null;
	}

	//以一个初始元素建立顺序队列
	public LinkQueue(T data){
		front = new Node(data, null);
		// 只有一个节点，都指向它
		rear = front;
		size ++;
	}

	//新元素插入队列  : 让原来的rear节点的next指向新的节点， 再让rear引用指向新节点
	public void insert(T data){
		//如果链表还是空链表的话
		if(front == null){
			front = new Node(data, null);
			rear = front;
		}
		else{
			Node newNode = new Node(data, null);
			//尾节点指向新增的节点
			rear.next = newNode;	
			rear = newNode;
		}
		size ++;
	}

	//移除或者删除队列 : front引用指向front后面的那个节点即可。
	public T remove(){
		Node oldNode = front;
		front = front.next;
		oldNode.next = null;
		size --;
		return oldNode.data;
	}

	//删除队列的最后一个元素
	public T element(){
		return rear.data;
	}
	
	//判断是否为空队列
	private boolean empty() {

		return size == 0;
	}

	//循环获取队列大小
	public int length(){

		return size;
	}

	//清空队列
	public void clear(){			
		front = null;
		rear = null;
		size = 0;
	}

	public String toString(){
		if(empty()){
			return "[]";
		}
		else{

			StringBuffer sb = new StringBuffer("[");
			for(Node current = front; 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> lq = new LinkQueue<Integer>();
		lq.insert(1);
		lq.insert(2);
		lq.insert(3);
		System.out.println(lq);
		lq.remove();
		lq.insert(4);
		System.out.println("删除一个元素和再添加一个元素的队列：" + lq);
	}

截图：

参考：《疯狂java 突破程序员基本功的16课》

以上是这篇的全部内容，如果有错误或需要改进的地方，请指教。谢谢！