栈和队列

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



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



先进后出-栈
如上图，入栈过程 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 指针的指向，建议画图加深印象。

栈和队列还是非常详细的