数据结构——LinkedQueue的实现

队列是一种先进先出(FIFO)的数据结构，LinkedQueue是用链表实现的，另外还可以用回环数组的方式实现。

LinkedQueue

import java.util.NoSuchElementException;

/**
 * 用单链表的形式实现链式队列
 * 该实现包含有一个指向尾部节点的引用，方便入队列操作的实现
 * @author Bingo
 *
 * @param <T>
 */
public class LinkedQueue<T> {
	private int size;
	private Node<T> head;
	private Node<T> tail;
	
	public LinkedQueue(){
		size = 0;
		tail = head = new Node<T>(null, null);
	}
	
	public int size(){
		return size;
	}
	
	public boolean isEmpty(){
		return size() == 0;
		//return head == tail;
	}
	
	/**
	 * 进队列，在链表的尾部添加新的元素
	 * @param ele
	 */
	public void enqueue(T ele){
		Node<T> newNode = new Node<T>(ele, null);
		tail.next = newNode;
		tail = newNode;
		size++;
	}
	
	/**
	 * 出队列，在链表的头部取出元素
	 * @return
	 */
	public T dequeue(){
		if(isEmpty())
			throw new NoSuchElementException("queue is empty.");
		
		T oldElement = head.next.element;
		head.next = head.next.next;
		size--;
		return oldElement;
	}
	
	/**
	 * 私有节点类,保存节点元素值和指向下一个节点的引用
	 * @author Bingo
	 *
	 * @param <T>
	 */
	private static class Node<T>{
		public T element;
		public Node<T> next;
		
		public Node(T element, Node<T> next){
			this.element  = element;
			this.next = next;
		}
	}

	@Override
	public String toString() {
		return "size = " + size();
	}
	
}