栈和队列
概念队列，是一种先进先出的结构，类似于我们日常生活中的各种排队https://ask.qcloudimg.com/http-save/yehe-1757319/d0c84c0706b9d0e700678dff12dadb79.png
先进先出-队列
栈，是先进后出的结构，就像弹匣一下
https://ask.qcloudimg.com/http-save/yehe-1757319/eeb9377b541d70da268ff96b00a79851.png
先进后出-栈
如上图，入栈过程 1 -> 3 -> 5，出栈顺序就是 5 -> 3 -> 1。
用双向链表实现队列和栈数据结构（一）| 链表 一节中，我们已经知道，双向链表由数据域和节点指针组成，有指向前一个节点的指针（last）和指向后一个节点的指针（next），头结点的last指向空，尾结点的next指向空。
https://ask.qcloudimg.com/http-save/yehe-1757319/64e8046d83432158bf206b81ff7b9658.png
双向链表
我们可以用双向链表来实现队列和栈。
双向链表实现队列https://ask.qcloudimg.com/http-save/yehe-1757319/417a893b0c8298a87f469e80ea567319.png
队列-从尾部插入，从头部取出
先定义双向链表：
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指向空。只进来一个节点时，头和尾都指向这个节点：
https://ask.qcloudimg.com/http-save/yehe-1757319/5a1456ad429410f5d545805979a4bbb4.png
插入第一个元素a
[*]push第二个元素b，那么它肯定排在a的后面，出的时候a先出。我们也是将元素b封装成一个链表节点，有前后两个指针，现在要考虑的是将b挂在哪里？应该是让b挂在a的next上，并且b的next指向null，同时让head节点不动，尾结点tail来到b的位置，如图所示：
https://ask.qcloudimg.com/http-save/yehe-1757319/ddf8148ae9a40838ca28b853769bf0ee.png
插入第二个元素b
[*]push第三个元素c，同样它是一个双向链表节点，让b的next指向它，并且设置它的next为null，同时head位置不动，tail移动到c的位置，如图所示：
https://ask.qcloudimg.com/http-save/yehe-1757319/2d4195c4c10b2e87092847e7df26936a.png
插入第三个元素c
以此类推，通过上述演示，我们可以得出，每当插入一个元素时，tail向后移动，即需要移动tail指针。
从队列取出元素
再来分析一下弹出元素如何做。由于先进先出，所以从头部弹出元素。
[*]第一次弹出，让头部指向原来头部的next，并将原来头部的value返回
https://ask.qcloudimg.com/http-save/yehe-1757319/ec34a598be7a88c42eacfe0ed18030e4.png
从头部弹出元素并返回
[*]继续弹出的话，需要继续移动head到上一次head的next节点，假设是c，并让c的last指向null
https://ask.qcloudimg.com/http-save/yehe-1757319/e229cd8a822240ebe33f76d78b214b6f.png
继续从头部弹出元素
从上述分析可以看出，从队列中取元素时，需要移动的是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指针，控制好这两个指针的指向就很容易写出来，建议用图画一下加深一下理解。
头部插入尾部取出（先插入的在尾部，所以从尾部取出，符合先进先出）的过程：
https://ask.qcloudimg.com/http-save/yehe-1757319/489f679314271471402b069f5aeda819.png
队列-从头部插入元素
一图胜千言，图上每一个插入动作都体现出了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 指针的指向，建议画图加深印象。
栈和队列还是非常详细的
页:
[1]