链表LinkedList实现队列

Queue.java（队列接口）

public interface Queue<E> {
	
	void enqueue(E e);//入队
	E dequeue();//出队
	E getFront();//获取队首元素
	int getSize();//获取队列中元素个数
	boolean isEmpty();//判断队列是否为空
}

LinkedListQueue.java（链表队列）
带尾节点的链表实现队列，没有设置虚拟头节点

//链表头是队列头，出队O(1);链表尾是队列尾,入队O(1)    
public class LinkedListQueue<E> implements Queue<E> {
	private class Node {// 内部类将节点设为私有 隐藏实现细节
		public E e;// 元素
		public Node next;// next指针

		public Node(E e, Node next) {
			this.e = e;
			this.next = next;
		}

		public Node(E e) {
			this(e, null);
		}

		public Node() {
			this(null, null);
		}

		@Override
		public String toString() {
			return e.toString();
		}
	}

	private Node head, tail;// 定义头节点，尾节点
	private int size;

	public LinkedListQueue() {
		// TODO Auto-generated constructor stub
		head = null;
		tail = null;
		size = 0;
	}

	@Override
	public void enqueue(E e) {
		// TODO Auto-generated method stub
		if (tail == null) { // tail == null是尾节点为空，也就是队列为空的时候，否则tail应该指向尾节点
			tail = new Node(e);// 传入要插入的节点
			head = tail;
		} else {
			tail.next = new Node(e);// 如果tail不为空，在tail.next处插入节点
			tail = tail.next;// tail后移
		}
		size++;
	}

	@Override
	public E dequeue() {
		// TODO Auto-generated method stub
		if (isEmpty())
			try {
				throw new Exception("队列为空");
			} catch (Exception e) {
				// TODO Auto-generated catch block
				e.printStackTrace();
			}
		Node retNode = head;// 出队的节点就是head所指向的节点
		head = head.next;// head后移
		retNode.next = null;
		if (head == null)// 如果队列中只有一个元素
			tail = null;
		size--;
		return retNode.e;
	}

	@Override
	public E getFront() {
		// TODO Auto-generated method stub
		if (isEmpty())
			try {
				throw new Exception("队列为空");
			} catch (Exception e) {
				// TODO Auto-generated catch block
				e.printStackTrace();
			}
		return head.e;
	}

	@Override
	public int getSize() {
		// TODO Auto-generated method stub
		return size;
	}

	@Override
	public boolean isEmpty() {
		// TODO Auto-generated method stub
		return size == 0;
	}

	public String toString() {
		StringBuilder res = new StringBuilder();
		res.append("Queue：front ");
		for (Node cur = head; cur != null; cur = cur.next)
			res.append(cur + "->");
		res.append("NULL tail");
		return res.toString();
	}
}

测试（main）

public class LinkedListQueueTest {
	public static void main(String[] args) {
		LinkedListQueue<Integer> loopqueue = new LinkedListQueue<>();
		for (int i = 0; i < 5; i++) {
			loopqueue.enqueue(i);
			System.out.println(loopqueue);
		}
		loopqueue.dequeue();
		System.out.println(loopqueue);
	}
}

测试结果

链表实现的队列的时间复杂度

入队：O(1)
出队：O(1)
查询队首元素：O(1)

实现队列的链表创建了尾节点tail，使得在链表尾部添加元素变得容易，复杂度为O(1)；但是在尾部删除元素需要遍历链表找到尾部元素的前一个节点，还是需要O(n)的复杂度，是不推荐的；所以使用链表头做队首，使用链表尾做队尾。