数据结构(二)| 队列与栈

>>强大,10k+点赞的 SpringBoot 后台管理系统竟然出了详细教程!

锲而舍之,朽木不折;锲而不舍,金石可镂。---荀子《劝学》

概念

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

数据结构(二)| 队列与栈
先进先出-队列

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

数据结构(二)| 队列与栈
先进后出-栈

如上图,入栈过程 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都指向空,

  1. 向队列push第一个元素(设为Node cur)的时候,将元素封装好,让它的next指向空,last指向空。只进来一个节点时,头和尾都指向这个节点:
数据结构(二)| 队列与栈
插入第一个元素a
  1. push第二个元素b,那么它肯定排在a的后面,出的时候a先出。我们也是将元素b封装成一个链表节点,有前后两个指针,现在要考虑的是将b挂在哪里?

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

数据结构(二)| 队列与栈
插入第二个元素b
  1. push第三个元素c,同样它是一个双向链表节点,让b的next指向它,并且设置它的next为null,同时head位置不动,tail移动到c的位置,如图所示:

    数据结构(二)| 队列与栈
    插入第三个元素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):数据结构(二)| 队列与栈