注意：这里是JAVA自学与了解的同步笔记与记录，如有问题欢迎指正说明
日撸 Java 三百行（17 天: 链表实现队列）一、你好，队列二、链表实现队列
1.结点定义2.链队列基本属性3.入队4.出队5.数据模拟 总结
一、你好，队列
今天我们来看线性表的第二个重要的结构：队列。
队列相比于栈来说在逻辑上就好理解多了，当别人问你，栈是啥，你可能要给他解释原理，但是队列就很简单了，你只要给他举一个例子：“排队”就行了。
定义：
队列是一种特殊的线性表，特殊之处在于它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作，和栈一样，队列是一种操作受限制的线性表。进行插入操作的端称为队尾，进行删除操作的端称为队头。
可见，相比于栈，队列是一种双端开放的受限队列，而并非栈那种单端式的。栈是单端可进可出，而队列是双端开放条件下，仅左端出右端进：
队列的数据元素又称为队列元素。在队列中插入一个队列元素称为入队（enqueue），从队列中删除一个队列元素称为出队（Dequeue）。因为队列只允许在一端插入，在另一端删除，所以只有最早进入队列的元素才能最先从队列中删除，故队列又称为先进先出（FIFO—first in first out）线性表。
因为这样的操作如同我们平时的排队一样，所以我们才称之为“ 队列 ”（Queue）
二、链表实现队列为什么不用顺序表实现？
栈我们使用的顺序表实现的，原因在于顺序表的空间开辟后，进行右侧单项的元素插入非常方便。
但是队列因为是双端开放的，若对顺序表左端进行操作时间的开销并不可观。但是，若要坚持使用顺序表完成队列也是可以，就需要对逻辑上的队列出入队操作进行适合于存储结构的优化（这个就是我们明天会介绍的循环队列）
那么如果我就想完成模拟逻辑上的队列出入队的模拟，怎么办？用链表来实现。
因为链表在确定插入节点的前驱后，插入的时间复杂度是比较可观的，而且代码表现也能清晰反应其逻辑本质。
下面我结合代码来分析下链表实现队列的过程：
代码如下：
class Node {
int data;
Node next;
public Node(int paraValue) {
data = paraValue;
next = null;
}// Of the constructor
}// Of class Node
因为是链表实现，因此有必要先设计好结点，这里按照正常的单链表结点设置即可。
2.链队列基本属性代码如下：
Node header;
Node tail;
public linkedQueue() {
header = new Node(-1);
tail = header;
}// Of the first constructor
public String toString() {
String resultString = "";
if (header.next == null) {
return "empty";
} // Of if
Node tempNode = header.next;
while (tempNode != null) {
resultString += tempNode.data + ", ";
tempNode = tempNode.next;
} // Of while
return resultString;
}// Of toString
链队列因为要保证尾部的插入与首部删除都能保证O(1)复杂度，而对于链表来说只要知道目标结点的前驱即可实现对于目标结点的O(1)复杂度删除与插入，所以我们事先于收，尾各准备了一个指针用于操作。
是否设置头结点会令对于首部与空队列的判断出现差异，这里我们设置是的带头结点的单链表，具体差异性我不会在本文中过多赘述，集体可参考非带头结点的链表删除与操作。
于是本代码的构造函数中预先设置了一个头结点。
3.入队入队很简单
代码如下：
public void enqueue(int paraValue) {
Node tempNode = new Node(paraValue);
tail.next = tempNode;
tail = tempNode;
}// Of enqueue
链表并没有鲜明的一个上限的说法，因此对于无论是用链表实现的栈还是队列，在设置进入容器的方法中我们都无需考虑上溢的问题，只需要：
1.创建元素
2.根据尾部指针插入元素
3.更新尾部指针（尾部指针前移）
即可。
代码如下：
public int dequeue() {
if (header == tail) {
System.out.println("No element in the queue");
return -1;
} // Of if
int resultValue = header.next.data;
header.next = header.next.next;
// The queue becomes empty.
if (header.next == null) {
tail = header;
} // Of if
return resultValue;
}// Of dequeu
}// Of enqueue
出队操作除了基本的判空情形，需要事先在程序开头说明。
还有一个非常特殊的情况，这种情况是双地址指针进行删除时需要额外注意的情况：
我们知道，通过第一个头结点删除首元素的过程本质上是一个指针跨越的过程，而被跨越的结点就是我们的删除结点。现在假设有一种情况，如果我们的队列当中只有一个有效结点：
那么自然，我们的rear一定仅仅指向这个结点，若这个时候执行header.next = header.next.next;就会无情把front所指的下一个结点删除同时rear也被无情架空了，所以这个时候我们需要重新赋值rear。
重新赋值这个过程可以在删除之前完成，也可以之后完成，这个没有什么影响，这里代码我们使用的是删除之后完成赋值操作：
// The queue becomes empty.
if (header.next == null) {
tail = header;
} // Of if
5.数据模拟
代码如下：
public static void main(String args[]) {
linkedQueue tempQueue = new linkedQueue();
System.out.println("Initialized, the list is: " + tempQueue.toString());
for (int i = 0; i < 5; i++) {
tempQueue.enqueue(i + 1);
} // Of for i
System.out.println("Enqueue, the queue is: " + tempQueue.toString());
tempQueue.dequeue();
System.out.println("Dequeue, the queue is: " + tempQueue.toString());
int tempValue;
for (int i = 0; i < 5; i++) {
tempValue = tempQueue.dequeue();
System.out.println("Looped delete " + tempValue + ", the new queue is: " + tempQueue.toString());
} // Of for i
for (int i = 0; i < 3; i++) {
tempQueue.enqueue(i + 10);
} // Of for i
System.out.println("Enqueue, the queue is: " + tempQueue.toString());
}// Of main
数据模拟中，按序完成入队操作。之后出队一次，然后循环出队，循环出队过程中出现一次对空现象，这里视察了对于队空出队非法操作的判别情况。
运行结果如下：
队列在计算机中的使用有些时候与栈是一致的，作为常见的受限线性表，栈与队列常常会共同出现。
队列相比于栈的不同最主要在于数据的有序出入特性，就是我们输入的数据顺序是什么样输出就是什么样。因此，在硬件中，某些只是用于数据缓存或者两个不同速度的设备之间创建缓冲区时（因为要保证输入输出方的数据必须按序一致），我们常常使用队列完成，比如操作系统中进程通信的Pipe文件，进程的消息缓存队列，磁盘缓冲区等。
然后队列鲜明的排队特性也可在许多底层和上层完成各形各色的数据内容排队，比如进程管理中的就绪、阻塞队列用来中转下一步处理的进程和尚未获得资源的进程；上层的算法设计中树的层次遍历与图的BFS中，我们常用队列缓存上一层遍历的数据（虽然栈也可以，但是栈的话顺序会逆序，不符合算法目标）
线性结构是计算机底层的结构（地址空间），任何逻辑上的线性结构都能很轻松与物理上的存储结构建立映射或者说抽象，也正因此，线性结构无论是对计算机有关算法、软件、硬件、上层、底层，都是非常重要且基础的结构。
而栈与队列作为线性结构的两架马车，也自然构成了计算机一切基础算法与硬软件设计的根基。
