【数据结构】受限制的线性表——队列

这篇具有很好参考价值的文章主要介绍了【数据结构】受限制的线性表——队列。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

【数据结构】受限制的线性表——队列,数据结构,数据结构,java,ide,后端
🧧🧧🧧🧧🧧个人主页🎈🎈🎈🎈🎈
🧧🧧🧧🧧🧧数据结构专栏🎈🎈🎈🎈🎈
🧧🧧🧧🧧🧧上一篇文章:特殊的线性表——栈🎈🎈🎈🎈🎈

前言

上一章我们讲了一种特殊的线性表只能在表尾进行插入和删除操作,接下来我们讲一个和栈很相似的数据结构,它也是一种特殊且所限制的线性表,它是只能在表头删除操作在表尾进行插入操作。

1.队列(Queue)

1.1队列的概念

队列:只允许在一端进行插入数据操作,在另一端进行删除数据操作的特殊线性表,队列具有先进先出FIFO(First In First Out) 入队列:进行插入操作的一端称为队尾(Tail/Rear) 出队列:进行删除操作的一端称为队头

2.2 队列的使用

在Java中,Queue是个接口,底层是通过链表实现的。
【数据结构】受限制的线性表——队列,数据结构,数据结构,java,ide,后端
【数据结构】受限制的线性表——队列,数据结构,数据结构,java,ide,后端
注意:Queue是个接口,在实例化时必须实例化LinkedList的对象,因为LinkedList实现了Queue接口。

2.3 队列模拟实现

我们这里通过链表来实现队列:
1.我们先将链表的框架搭建一下,代码如下:

public class MyQueue {
    static class ListNode {
        public int val;
        public ListNode prev;
        public ListNode next;
        public ListNode(int val) {
            this.val = val;
        }
    }
    public ListNode head;
    public ListNode last;
}

2.方法的实现:

2.1入队(offer)

//offer 入队
    public void offer(int val) {
        ListNode node = new ListNode(val);
        //1.空节点
        if(head == null) {
            head = node;
            last = node;
        } else {
            //2.不为空节点,尾插法。
            last.next = node;
            node.prev = last;
            last = node;
        }
    }

2.2 出队(poll)

   //poll 出队
    public int poll() {
        //1.判断队是否为空
        if(isEmpty()) {
            //1.1队为空,抛出队为空的异常
           throw new QueueEmptyException("队空异常!!!!");
        } else {
            //2.队中是否只有一个元素
            int val = head.val;
            if(head.next == null) {
                //2.1只有一个元素
                head = null;
                last = null;
                return val;
            } else {
                //2.2队中不只一个元素,删头节点
                head = head.next;
                head.prev = null;
                return val;
            }
        }
    }
    public boolean isEmpty() {
        return head == null;
    }

2.3 peek

//peek
    public int peek() {
        //1.判断队是否为空
        if(isEmpty()) {
            //1.1队为空,抛出队为空的异常
            throw new QueueEmptyException("队空异常!!!!");
        } else {
            //1.2队不空,直接返回队头元素
             return head.val;
        }
    }

2.4 判断队列空

public boolean isEmpty() {
        return head == null;
    }

3.我这写一个队满报异常的代码

public class QueueEmptyException extends RuntimeException{
    public QueueEmptyException() {
    }

    public QueueEmptyException(String message) {
        super(message);
    }
}

2.4 循环队列

在实现队列可以通过链表来实现,还可以通过顺序表来实现,但在用顺序表来实现的时候,我们会发现,当队中在一边出队一边入队,会出现空间浪费的情况。
【数据结构】受限制的线性表——队列,数据结构,数据结构,java,ide,后端
那我们怎么解决这个问题? 我们就提出将一个数组围成一个圆圈的样子,那么这么就不会把空间给浪费,像这样似的:
【数据结构】受限制的线性表——队列,数据结构,数据结构,java,ide,后端
这时候会出现一个问题那就是怎么去区分这个队中是满还是空,在解决这个问题之前我先分享一个很有趣的方法:关于数组下标在循环的一个小tip 下一个下标等于(此时的下标+1)%数组的长度
用公式表示:index =(rear+1)%elem.length
【数据结构】受限制的线性表——队列,数据结构,数据结构,java,ide,后端

我们就这个问题有三种方式去解决分别为:
1.size计数法
我们定义一个变量usedSize来记录队中的元素个数,当usedSize等于0,说明队中为空,当usedSize等于数组的长度,那么队满。
在入队的时候每入队一个元素usedSize就加1,在出队的时候usedSize就减1.
代码实现:

public class CircularQueueSize {
    public int[] elem;
    public int front;
    public int rear;
    public int usedSize;
    public CircularQueueSize() {
       elem = new int[8];
    }
    //入队
    public void offer(int val) {
        if(isFull()) {
            throw new CircularQueueSizeFullException("队满异常!!!");
        } else {
            elem[rear] = val;
            rear = (rear+1) % elem.length;
            usedSize++;
        }
    }
    //出队
    public int poll() {
        //1.判断队空不空
        if(isEmpty()) {
            //1.1队空
            throw new CircularQueueSizeEmptyException("循环队列空异常!!!");
        } else {
            //1.2队不空
            int val = elem[front];
            front = (front+1) % elem.length;
            usedSize--;
            return val;
        }
    }
    //判断队中是否空
    public boolean isEmpty() {
        return usedSize == 0;
    }
    //判断循环队列已满
    public boolean isFull() {
        return usedSize == elem.length;
    }
    //Front 获取队头元素
    public int  Front () {
        if(isEmpty()) {
            return -1;
        }
        return elem[front];
    }
    //Rear 获取队尾元素
    public int Rear() {
        if(isEmpty()) {
            return -1;
        }
        int ret = (rear == 0) ? elem.length : rear-1;
        return elem[ret];
    }
}

2.flg标志法
我们定义一个boolean类型的flg标志位,一开始为false,每入队一个元素flg就置为true,每出队一个元素flg置为false。
判断队满队空的条件
队满:队头等于队尾并且flg等于ture
队空:队头等于队尾并且flg等于false
代码实现:

public class CircularQueueFlg {
    public int[] elem;
    public int front;
    public int rear;
    public boolean flg;
    public int usedSize;
    public CircularQueueFlg() {
        elem = new int[8];
    }
    //入队
    public void offer(int val) {
        if(isFull()) {
            throw new CircularQueueSizeFullException("队满异常!!!");
        }
            elem[rear] = val;
             flg = true;
            rear = (rear+1) % elem.length;
    }
    //出队
    public int poll() {
        //1.判断队空不空
        if(isEmpty()) {
            //1.1队空
            throw new CircularQueueSizeEmptyException("循环队列空异常!!!");
        } else {
            //1.2队不空
            int val = elem[front];
            flg = false;
            front = (front+1) % elem.length;
            return val;
        }
    }
    //判断队中是否空
    public boolean isEmpty() {
        return (front == rear) && (flg == false);
    }
    //判断循环队列已满
    public boolean isFull() {
       return (front == rear) && (flg == true);
    }
    //Front 获取队头元素
    public int  Front () {
        if(isEmpty()) {
            return -1;
        }
        return elem[front];
    }
    //Rear 获取队尾元素
    public int Rear() {
        if(isEmpty()) {
            return -1;
        }
        int ret = (rear == 0) ? elem.length : rear-1;
        return elem[ret];
    }
}

3.空间牺牲法
我们牺牲一个空间来实现循环队列判断队满和队空
队满:index = 队头 index (队尾此刻的下标+1)%数组的长度
队空:队尾等于队头
代码实现:

public class CircularQueueSpace {
    public int[] elem;
    public int front;
    public int rear;
    public  CircularQueueSpace() {
        elem = new int[8];
    }
    //入队
    public void offer(int val) {
        if(isFull()) {
            throw new CircularQueueSizeFullException("队满异常!!!");
        } else {
            elem[rear] = val;
            rear = (rear+1) % elem.length;
        }
    }
    //出队
    public int poll() {
        //1.判断队空不空
        if(isEmpty()) {
            //1.1队空
            throw new CircularQueueSizeEmptyException("循环队列空异常!!!");
        } else {
            //1.2队不空
            int val = elem[front];
            front = (front+1) % elem.length;
            return val;
        }
    }
    //判断队中是否空
    public boolean isEmpty() {
        return front == rear;
    }
    //判断循环队列已满
    public boolean isFull() {
        return front == (rear+1) % elem.length;
    }
    //Front 获取队头元素
    public int  Front () {
        if(isEmpty()) {
            return -1;
        }
        return elem[front];
    }
    //Rear 获取队尾元素
    public int Rear() {
        if(isEmpty()) {
            return -1;
        }
        int ret = (rear == 0) ? elem.length-1 : rear-1;
        return elem[ret];
    }
}

3. 双端队列 (Deque)

双端队列(deque)是指允许两端都可以进行入队和出队操作的队列,deque 是 “double ended queue” 的简称。那就说明元素可以从队头出队和入队,也可以从队尾出队和入队。
【数据结构】受限制的线性表——队列,数据结构,数据结构,java,ide,后端
eque是一个接口,使用时必须创建LinkedList的对象。
在实际工程中,使用Deque接口是比较多的,栈和队列均可以使用该接口。

Deque<Integer> stack = new ArrayDeque<>();//双端队列的线性实现
Deque<Integer> queue = new LinkedList<>();//双端队列的链式实现

希望大家可以给我点点关注,点点赞,并且在评论区发表你们的想法和意见,我会认真看每一条评论,你们的支持就是我的最大鼓励。🌹🌹🌹🌹🌹🌹🌹🌹🌹🌹🌹🌹🌹🌹文章来源地址https://www.toymoban.com/news/detail-846507.html

到了这里,关于【数据结构】受限制的线性表——队列的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 线性数据结构:数组、受限数组(栈、队列)、线性表

      数组(Array)是有序的元素序列。属于线性结构(有且仅有一个前驱、有且仅有一个后继)。   数组的关键在于在内存中的物理地址对应的是 一段连续的内存 。这意味着如果想要在任意位置删除/新增一个元素,那么该位置往后的所有元素,都需要往前挪/往后挪一个位

    2024年03月09日
    浏览(53)
  • 数据结构01-线性结构-链表栈队列-栈篇

    线性结构-栈 本系列为C++数据结构系列,会介绍 线性结构,简单树,特殊树,简单图等。本文为线性结构部分。 线性结构 【 3 】链表:单链表、双向链表、循环链表 【 3 】栈 【 3 】队列 栈是Stack一个后进先出Last In First Out,LIFO的线性表,他要求只在表尾对数据执行删除和插

    2024年02月16日
    浏览(42)
  • 【数据结构】线性表之栈、队列

    前面两篇文章讲述了关于线性表中的顺序表与链表,这篇文章继续讲述线性表中的 栈和队列。 这里讲述的两种线性表与前面的线性表不同,只允许在一端入数据,一段出数据,详细内容请看下面的文章。 顺序表与链表两篇文章的链接: 线性表之顺序表 线性表之链表 注意:

    2024年02月06日
    浏览(62)
  • 【数据结构篇】线性表2 —— 栈和队列

    前言:上一篇我们介绍了顺序表和链表 (https://blog.csdn.net/iiiiiihuang/article/details/132615465?spm=1001.2014.3001.5501), 这一篇我们将介绍栈和队列,栈和队列都是基于顺序表和链表来实现的 目录 栈(Stack) 什么是栈 ? 栈的方法 和 使用 栈的模拟实现  先初始化一下栈  往栈里插入

    2024年02月09日
    浏览(41)
  • 【数据结构初阶】六、线性表中的队列(C语言 -- 链式结构实现队列)

    ========================================================================= 相关代码gitee自取 : C语言学习日记: 加油努力 (gitee.com)  ========================================================================= 接上期 : 【数据结构初阶】五、线性表中的栈(C语言 -- 顺序表实现栈)_高高的胖子的博客-CSDN博客  

    2024年02月08日
    浏览(43)
  • C语言数据结构——线性表之栈和队列

    为什么会定义栈和队列这两种数据结构呢? 原因在于: 之所以会定义栈和队列这样的数据结构 是因为他们有两大特性 : 第一: 他们可以保存程序运行路径中各个点的信息,以便用于回溯操作或其他需要访问已经访问过的节点信息的操作。 比如: 栈用于解决迷宫问题,就

    2023年04月11日
    浏览(113)
  • 数据结构笔记NO.1(绪论、线性表、栈队列和矩阵的压缩存储)

    1、数据结构 三要素 :逻辑结构、存储结构(物理结构)、数据的运算。 (1)逻辑结构:是指数据元素之间的逻辑关系,即从逻辑关系上描述数据,它与数据的存储无关,是独立于计算机的。 (2)存储结构(物理结构):是指数据在计算机中的表示(又称映像),是用计算机语

    2024年02月04日
    浏览(40)
  • 数据结构之线性表的类型运用Linear Lists: 数组,栈,队列,链表

    定义 一个最简单,最基本的数据结构。一个线性表由多个相同类型的元素穿在一次,并且每一个元素都一个前驱(前一个元素)和后继(后一个元素)。 线性表的类型 常见的类型:数组、栈、队列、链表 这些不同数据结构的特性可以解决不同种类的问题 题面 题目描述 有

    2024年02月12日
    浏览(47)
  • Java数据结构学习和源码阅读(线性数据结构)

    链表的数据结构 一组由节点组成的数据结构,每个元素指向下一个元素,是线性序列。 最简单的链表结构: 数据 指针(存放执行下一个节点的指针) 不适合的场景: 需要循环遍历将导致时间复杂度的提升 链表分类—单向链表 链表结构: 数据 指针 Next(指向下一个节点)

    2024年02月12日
    浏览(46)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包