数据结构（二）| 队列与栈
锲而舍之，朽木不折；锲而不舍，金石可镂。---荀子《劝学》
概念
队列，是一种先进先出的结构，类似于我们日常生活中的各种排队
先进先出-队列
栈，是先进后出的结构，就像弹匣一下
先进后出-栈
如上图，入栈过程 1 -> 3 -> 5，出栈顺序就是 5 -> 3 -> 1。
用双向链表实现队列和栈
数据结构（一）| 链表 一节中，我们已经知道，双向链表由数据域和节点指针组成，有指向前一个节点的指针（last）和指向后一个节点的指针（next），头结点的last指向空，尾结点的next指向空。
双向链表
我们可以用双向链表来实现队列和栈。
双向链表实现队列
队列-从尾部插入，从头部取出
先定义双向链表：
public class Node<T> {
public T value;
public Node last;
public Node next;
public Node(T value) {
this.value = value;
}
}
根据队列的特性，先进先出，入队时元素加入到队尾（tail），出队时从队列头部（head）出，因此，入队push和出队poll方法的实现需要定义两个辅助Node head和tail即可。
向对列插入元素
一开始head和tail都指向空，
- 向队列push第一个元素（设为Node cur）的时候，将元素封装好，让它的next指向空，last指向空。只进来一个节点时，头和尾都指向这个节点：
插入第一个元素a
- push第二个元素b，那么它肯定排在a的后面，出的时候a先出。我们也是将元素b封装成一个链表节点，有前后两个指针，现在要考虑的是将b挂在哪里？ 应该是让b挂在a的next上，并且b的next指向null，同时让head节点不动，尾结点tail来到b的位置，如图所示：
插入第二个元素b
- push第三个元素c，同样它是一个双向链表节点，让b的next指向它，并且设置它的next为null，同时head位置不动，tail移动到c的位置，如图所示：
插入第三个元素c
以此类推，通过上述演示，我们可以得出，每当插入一个元素时，tail向后移动，即需要移动tail指针。
从队列取出元素
再来分析一下弹出元素如何做。由于先进先出，所以从头部弹出元素。
- 第一次弹出，让头部指向原来头部的next，并将原来头部的value返回
从头部弹出元素并返回
- 继续弹出的话，需要继续移动head到上一次head的next节点，假设是c，并让c的last指向null
继续从头部弹出元素
从上述分析可以看出，从队列中取元素时，需要移动的是head节点。
代码实现：
public class MyQueue {
//借助链表实现队列
private Node head;
private Node tail;
//入队操作
public void push(T value) {
//封装一个节点，保存其值，然后考虑将该节点挂在哪个位置
Node<T> cur = new Node<>(value);
if (head == null) {
//一开始队列为空的时候，插入一个元素后，让head和tail都移动到当前节点
head = cur;
tail = cur;
} else {
//头结点不是空的情况，插入后，尾指针移动
cur.last = tail;
tail.next = cur;
tail = cur;
}
}
//出队-获取队列头部元素
public T poll() {
if (head == null) {
System.out.println("队列空了");
return null;
}
Node cur = head;
//让head的下一个节点成为新的头结点
if (head == tail) {
//只有一个元素了
head = null;
tail = null;
} else {
//移动head
head = head.next;
head.last = null;
cur.next = null;
}
return cur.value;
}
}
TIP：上述用双向链表实现的是从尾部插入元素，从头部取出元素。双向链表的节点有两个指针，可以灵活的控制从队列的哪个方向插入和取出数据：也就是说可以用双向链表实现双端队列。
实现双端队列
双端队列，既可以从尾部插入头部取出（前面已实现），也可以从头部插尾部取出。
用链表实现队列（还有后面要实现的栈结构），玩的就是head和tail指针，控制好这两个指针的指向就很容易写出来，建议用图画一下加深一下理解。
头部插入尾部取出（先插入的在尾部，所以从尾部取出，符合先进先出）的过程：
队列-从头部插入元素
一图胜千言，图上每一个插入动作都体现出了head、tail指针的变化，我们来根据这个图实现双端队列的另一半：
public class DoubleEndsQueue<T> {
//上来先定义head和tail
private Node<T> head;
private Node<T> tail;
//从尾部插入头部取出的实现见MyQueue的push和poll方法，此处略
//从头部插入
public void addFromHead(T value) {
//宗旨：移动head
Node<T> cur = new Node<>(value);
if (head == null) {
head = cur;
tail = cur;
} else {
cur.next = head;
head.last = cur;
head = cur;
}
}
//从尾部取出
public T popFromBottom() {
if (head == null) {
system.out.println("队列为空");
return null;
}
Node<T> cur = tail;
if (head == tail) {
head = null;
tail = null;
} else {
tail = tail.last;
tail.next = null;
cur.last = null;
}
return cur.value;
}
}
双向链表实现栈
栈的结构和队列在结构上是相似的，就是出入栈和队列的出入在方向上有差别。
我们可以基于上面实现的双端队列（内部是用双向链表实现）来实现栈：只要符合先进后出的规则就行：addFromHead和popFromHead、addFromBottom和popFromBottom。
public class MyStack<T> {
private DoubleEndsQueue<T> queue;
public MyStack() {
queue = new DoubleEndsQueue<T>();
}
public void push(T value) {
queue.addFromHead(value);
}
public T pop() {
return queue.popFromHead();
}
}
小结
队列的先进先出 和 栈的先进后出 结构，基于双向链表指针的灵活性，很容易实现。
实现的要诀就是控制头 head、尾 tail 指针的指向，建议画图加深印象。