大话数据结构九：队列的链式存储结构（链队列）

1.链队列的特点：

链队列其实就是单链表，只不过它是先进先出的单链表，为了实现方便，程序中设置了队头（front），队尾（rear）两个指针。

2. Java使用链表实现队列:

//结点类，包含结点的数据和指向下一个节点的引用
public class Node<E> {
	private E data; // 数据域
	private Node<E> next; // 指针域保存着下一节点的引用

	public Node() {
	}

	public Node(E data) {
		this.data = data;
	}

	public Node(E data, Node<E> next) {
		this.data = data;
		this.next = next;
	}

	public E getData() {
		return data;
	}

	public void setData(E data) {
		this.data = data;
	}

	public Node<E> getNext() {
		return next;
	}

	public void setNext(Node<E> next) {
		this.next = next;
	}
}

// Java实现链队列
public class LinkedQueue<T> {
	private Node<T> front; // 记住队头结点
	private Node<T> rear; // 记住队尾结点
	private int size; // 记住链表长度

	public LinkedQueue() {
		front = rear = null;
		size = 0;
	}

	// 将元素追加到队列尾部
	public boolean enqueue(T data) {
		Node<T> newNode = new Node<T>(data);
		if (isEmpty()) { // 判断队列是否为空
			front = rear = newNode;
		} else {
			rear.setNext(newNode); // 将新进来的结点设置为尾结点
			rear = newNode;
		}
		size++;
		System.out.println(data + "入队..");
		return true;
	}

	// 队列头部的第一个元素出队
	public T dequeue() {
		T data = null;
		if (isEmpty()) {
			System.out.println("队列为空,无法出队..");
		} else {
			if (front.getNext() == null) { // 队列中只有一个结点
				rear = null;
			}
			data = front.getData();
			front = front.getNext(); // 将原队头的下一个结点设置为队头
			System.out.println(data + "出队..");
			size--;
		}
		return data;
	}

	// 获取链队列的长度
	public int size() {
		return size;
	}

	// 判断链队列是否为空
	public boolean isEmpty() {
		return size == 0;
	}
	
	// 清空链队列
	public void clear() {
		front = rear = null;
		size = 0;
	}
	
	// 打印队列中的元素
	public void display() {
		if (!isEmpty()) {
			Node<T> nextNode = front;
			for (int i = 0; i < size(); i++) {
				System.out.print(" " + nextNode.getData());
				nextNode = nextNode.getNext();
			}
		}
	}
	
	// 测试方法
	public static void main(String[] args) {
		LinkedQueue<String> queue = new LinkedQueue<String>();
		queue.enqueue("张三");
		queue.dequeue();
		queue.dequeue();
		queue.enqueue("李四");
		queue.enqueue("王五");
		queue.enqueue("赵六");
		queue.dequeue();
		queue.enqueue("田七");
		queue.dequeue();
		queue.enqueue("周八");
		System.out.println("队列中元素个数为: " + queue.size());
		System.out.print("打印队列中的元素: ");
		queue.display();
	}
}

3. 链队列和循环队列比较：

1.) 时间上：循环队列事先申请好空间，使用期间不释放。链队列每次申请和释放结点存在一些时间开销，如果入队出队操作频繁，链队列性能稍差。

2.) 空间上：循环队列必须有一个固定长度，所以就有了存储元素个数和空间浪费的问题。链队列不存在这个问题，所以在空间上更为灵活。

4. 什么时候使用链队列：

1.) 在可以确定队列长度最大值的情况下，建议用循环队列。

2.) 如果无法预估队列的长度，则用链队列 。