作者：行百里er

博客：https://chendapeng.cn (opens new window)

提示

这里是 行百里er 的博客：行百里者半九十，凡事善始善终，吾将上下而求索！

引言

队列，是一种先进先出的结构，类似于我们日常生活中的各种排队

栈，是先进后出的结构，就像弹匣一下

如上图，入栈过程 1 -> 3 -> 5，出栈顺序就是 5 -> 3 -> 1。

用双向链表实现队列和栈

链表 (opens new window) ，我们已经知道，双向链表由数据域和节点指针组成，有指向前一个节点的指针（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都指向空，

1. 向队列push第一个元素（设为Node cur）的时候，将元素封装好，让它的next指向空，last指向空。只进来一个节点时，头和尾都指向这个节点：

2. push第二个元素b，那么它肯定排在a的后面，出的时候a先出。我们也是将元素b封装成一个链表节点，有前后两个指针，现在要考虑的是将b挂在哪里？

   应该是让b挂在a的next上，并且b的next指向null，同时让head节点不动，尾结点tail来到b的位置，如图所示：

3. push第三个元素c，同样它是一个双向链表节点，让b的next指向它，并且设置它的next为null，同时head位置不动，tail移动到c的位置，如图所示：

   

以此类推，通过上述演示，我们可以得出，每当插入一个元素时，tail向后移动，即需要移动tail指针。

从队列取出元素

再来分析一下弹出元素如何做。由于先进先出，所以从头部弹出元素。

1. 第一次弹出，让头部指向原来头部的next，并将原来头部的value返回

   

2. 继续弹出的话，需要继续移动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 指针的指向，建议画图加深印象。

---

首发公众号 行百里er ，欢迎老铁们关注阅读指正。