专栏首页JavaJourney数据结构(二)| 队列与栈

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

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

概念

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

先进先出-队列

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

先进后出-栈

如上图,入栈过程 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返回

从头部弹出元素并返回

  1. 继续弹出的话,需要继续移动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

本文参与 腾讯云自媒体分享计划 ,欢迎热爱写作的你一起参与!

作者:行百里er
原始发表时间:2021-06-11
如有侵权,请联系 cloudcommunity@tencent.com 删除。
登录 后参与评论
0 条评论

相关文章

  • 数据结构:栈与队列

    工程代码 Github: Data_Structures_C_Implemention -- Stack & Queue

    半纸渊
  • 数据结构笔记(二):栈、队列

    4、栈可以用数组实现,也可以用链表实现。用数组实现的栈叫做顺序栈,用链表实现的栈叫做链式栈。

    free赖权华
  • 数据结构(三):栈与队列

    3.1❶若按教科书3.1.1节中图3.1(b)所示铁道进行车厢调度(注意:两侧铁道均为单向行驶道),则请回答: ? (1) 如果进站的车厢序列为123,则可能...

    云时之间
  • 数据结构之栈与队列(优先队列/堆)

    栈与队列是两种重要的特殊线性表,从结构上讲,两者都是线性表,但从操作上讲,两者支持的基本操作却只是线性表操作的子集,是操作受限制的线性表。栈与队列两者最大的区别...

    我是东东东
  • JS数据结构与算法 — 栈与队列

    栈与队列分别是两种数据结构,不同语言对于栈和队列有着不同的声明 栈数据结构的特点是 FILO(first in last out) 即先进后出,队列则是 FIF...

    用户9914333
  • 数据结构与算法(三)栈与队列

    一、栈   栈(stack)是限定仅在表尾进行插入和删除操作的线性表,我们把允许插入和删除的一端称为栈顶(top),另一端称为栈底(bottom),不含任何数...

    matinal
  • 数据结构—栈/队列

    仔细一想 似乎自己已经有半年已经没有手写栈/队列了 STL里面的栈/队列好用是好用但是速度令人堪忧啊。 于是乎今天自己手写了一份栈&&队列, 以后就用这种格式了...

    attack
  • 数据结构:栈&队列

    栈的顺序存储称为顺序栈,它是利用一组地址连续的存储单元存放自栈底到栈顶的数据元素,同时附设一个指针(top)指示当前栈顶的位置。

    HLee
  • 数据结构 栈&队列

    2-4 依次在初始为空的队列中插入元素a,b,c,d以后,紧接着做了两次删除操作,此时的队头元素是( ) 删除,移动头指针; 增加,移动尾指针; 删除a,b ,...

    Kindear
  • JavaScript 数据结构(2-1):栈与队列-栈篇

    栈和队列是web开发中最常用的两种数据结构。绝大多数用户,甚至包括web开发人员,都不知道这个惊人的事实。如果你是一个程序员,那么请听我讲两个启发性的例子:使用...

    疯狂的技术宅
  • 数据结构 | 使用Kotlin实现栈与队列

    虽然我们上面实现了普通队列,但是普通的队列也有存在性能问题,比如当我们移除队首元素时,算法复杂度为O(n),这是我们不能接受的。

    Petterp
  • JavaScript 数据结构(2-2):栈与队列-队列篇

    当我们想要按顺序添加数据或删除数据时,可以使用栈结构。根据它的定义,栈可以只删除最近添加的数据。如果想要删除最早的数据该怎么办呢?这时我们希望使用名为queue...

    疯狂的技术宅
  • 算法与数据结构(二):队列

    队列也是一种线性的数据结构,它与链表的区别在于链表可以在任意位置进行插入删除操作,而队列只能在一端进行插入,另一端进行删除。它对应于现实世界中的排队模型。队列有...

    Masimaro
  • 数据结构与前端(二)-队列

    因为单链队列在出队操作的时候需要 O(n) 的时间复杂度,所以引入了循环队列。循环队列的出队操作平均是 O(1) 的时间复杂度。

    前端迷
  • 数据结构(三)-- 栈、队列

    栈(stack)又名堆栈,它是一种运算受限的线性表。限定仅在表尾进行插入和删除操作的线性表。这一端被称为栈顶,相对地,把另一端称为栈底。向一个栈插入新元素又称作...

    看、未来
  • 栈与队列

    当某个数据集合只涉及在一端插入和删除数据,并且满足后进先出、先进后出的特性,就可以选择栈这种数据结构。 用数组实现的栈称为顺序栈,用链表实现的栈称为链表栈 ...

    Yif
  • 数据结构与算法(四)| 队列、栈与Java集合

    比如,实现图的宽度优先遍历,但是要求用栈实现;实现图的深度优先遍历,但是要求用队列实现。

    行百里er
  • 数据结构 - 栈和队列

    栈(stack) 是一个特殊的线性表,是限定仅在一端(通常是表尾)进行插入和删除操作的线性表。表尾的一端有其特殊含义,称为 栈顶(top) ,相应地,表头称为 ...

    忆想不到的晖

扫码关注腾讯云开发者

领取腾讯云代金券