专栏首页三分恶的专栏重学数据结构(三、队列)

重学数据结构(三、队列)

1、队列的定义和特点

和上一篇的栈相反,队列(queue)是一种先进先出(First In First Out, FIFO)的线性表。

它只允许在表的一端进行插入,而在另一端删除元素。这和日常生活中的排队是一致的,最早进入队列的元素最早离开。

在队列中,允许插入的一端称为队尾(rear), 允许 删除的一端则称为队头(front)。出队列和入队列示意图如下:

2、队列的基本操作

队列的基本运算和堆栈类似,包含判空、获取长度、入队、出队、出队、取队头(不删除队头)等。

我们这里定义一个队列的接口。

/**
 * @Author 三分恶
 * @Date 2020/8/27
 * @Description 队列
 */
public interface Queue {
    public boolean isEmpty();     //判空
    public int size();            //获取队列容量
    public void enQueue(Object element);   //入队
    public Object deQueue();              //出队
    public Object getHead();              //取队首元素
}

队列是一种受限的线性表,同样有顺序和链式两种实现。

3、顺序队列

这里顺序队列通过可扩容数组来实现。

在类里标记了队头和对尾的下标。

入队时,队尾往后移动,队头保持不变,出队是队头往后移动,队尾保持不变。

为什么不保持队头指向0?因为如果队首指向0,那么出队的时候需要将数组前移,时间复杂度为O(n)。使用了队头和队尾标记之后,出队时队头往后移动一位,这样避免了元素的移动。

/**
 * @Author 三分恶
 * @Date 2020/8/27
 * @Description 顺序队列
 */
public class ArrayQueue implements Queue{
    private static  int defaultSize=15;   //默认容量
    private int size;                    //实际容量:实际存储元素个数
    private Object[] data;               //存放元素的数组
    private int front=0;                   //队头(下标)
    private int rear=0;                    //队尾(下标)

    /**
     * 无参构造方法:按默认容量构造元素数组
     */
    public ArrayQueue(){
        data=new Object[defaultSize];
    }

    /**
     * 有参构造方法:指定元素数组容量
     * @param capacity
     */
    public ArrayQueue(int capacity){
        data=new Object[capacity];
    }

    /**
     * 判空
     * @return
     */
    public boolean isEmpty() {
        return size==0;
    }

    /**
     * 获取队列元素个数
     * @return
     */
    public int size() {
        return size;
    }

    /**
     * 入队
     * @param element
     */
    public void enQueue(Object element) {
        //如果队满
        if (size==data.length&&front==0){
            //真队满,扩容
            if (front==0){
                //扩容两倍的新数组
                Object [] newData=new Object[size<<1];
                //拷贝数组
                System.arraycopy(data,0,newData,0,size);
                data=newData;
            }else{
                //假队满:前移元素
                //所有数据前移front位
                for (int i=front;i<size;i++){
                    data[i-front] = data[i];
                }
                //队尾前移front位
                rear-=front;
                //队头指向0
                front=0;
            }
        }
        //队尾插入元素
        data[rear]=element;
        rear++;
        size++;
    }

    /**
     * 出队
     * @return
     */
    public Object deQueue() {
        if (isEmpty()){
            throw new RuntimeException("队空");
        }
        //取队头元素
        Object f=data[front];
        //队头数组元素指向null,帮助gc
        data[front]=null;
        //队首指向下一元素
        front++;
        //元素个数减1
        size--;
        //返回队首元素
        return f;
    }

    /**
     * 取队首元素(不删除队首元素)
     * @return
     */
    public Object getHead() {
        if (isEmpty()){
            throw new RuntimeException("队空");
        }
        return data[front];
    }
}

时间复杂度分析:

  • 入队:平均O(1),最坏情况(扩容)O(n)
  • 出队:O(1)
  • 取队首:O(1)

3、链式队列

这里使用单向链表来实现链式队列。

入队是将队尾指向插入的新元素,出队是将队头指向队头的下一个元素。

/**
 * @Author 三分恶
 * @Date 2020/8/27
 * @Description
 */
public class LinkedQueue implements Queue{

    /**
     * 节点类
     * @param <T>
     */
    class Node<T>{
        private Object data;    //数据
        private Node next;    //下一节点
        Node(Object it, Node nextVal){
            this.data=it;
            this.next=nextVal;
        }
    }

    private Node front;       //队头
    private Node rear;        //队尾
    private int size;         //队列元素个数


    /**
     * 判空
     * @return
     */
    public boolean isEmpty() {
        return size==0;
    }

    public int size() {
        return size;
    }

    /**
     * 入栈
     * @param element
     */
    public void enQueue(Object element) {
        Node node=new Node(element,null);
        //如果队列为空
        if (rear==null){
            rear=node;
            front=node;
        }else{
            rear.next=node;
        }
        size++;
    }

    /**
     * 出队
     * @return
     */
    public Object deQueue() {
        //队列为空
        if (front==null){
            throw new RuntimeException("队列为空");
        }
        //队头
        Node node=front;
        front=front.next;
        size--;
        return node.data;
    }

    /**
     * 取队头元素
     */
    public Object getHead() {
        //队列为空
        if (front==null){
            throw new RuntimeException("队列为空");
        }
        return front.data;
    }
    
}

时间复杂度分析:

  • 入队:O(1)
  • 出队:O(1)
  • 取队首:O(1)

除此之外,顺序队列有变种循环队列,当rear到达数组的最大下标时,重新指回数组下标为0的位置; 链式队列有双端队列,队头、队尾都可以进行入队、出队操作的队列,可以通过双向链表实现;

4、java中的队列

java中有一个队列接口java.util.Queue,定义了队列的一些方法。

它有一个子接口,java.util.Deque,定义了双端队列的方法。

LinkedList实现了java.util.Deque接口,所以LinkedList能作为队列也能作为双端队列使用。详见LinkedList源码阅读笔记

源码地址:https://gitee.com/LaughterYoung/data-structure-learn.git

参考:

【1】:邓俊辉 编著. 《数据结构与算法》 【2】:王世民 等编著 . 《数据结构与算法分析》 【3】: Michael T. Goodrich 等编著.《Data-Structures-and-Algorithms-in-Java-6th-Edition》 【4】:严蔚敏、吴伟民 编著 . 《数据结构》 【5】:程杰 编著 . 《大话数据结构》 【6】:看完这篇你还不知道这些队列,我这些图白作了

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 重学数据结构(二、栈)

    比如上面的羽毛球筒,只能将最顶端的羽毛球移出,也只能将新的羽毛球放到最顶端——这两种操作分别称作入栈( Push)和出栈( Pop)。入栈和出栈的示意图如下:

    三分恶
  • Java Review (四、流程控制)

    不论哪一种编程语言,都会提供两种基本的流程控制结构:分支结构和循环结构。其中分支结构用 于实现根据条件来选择性地执行某段代码,循环结构则用于实现根据循环条件重复...

    三分恶
  • Java Review(三十五、注解)

    注解能被用来为程序元素( 类、 方法、 成员变量等) 设置元数据。 值得指出的是, 注解不影响程序代码的执行, 无论增加、 删除注解, 代码都始终如一地执行。 ...

    三分恶
  • R语言之可视化⑨火山图

    ====================================== 火山图可以方便直观地展示两个样本间基因差异表达的分布情况。通常横坐标用log2(...

    用户1359560
  • JS相关概念

    小胖
  • WebView性能、体验分析与优化

    在App开发中,内嵌WebView始终占有着一席之地。它能以较低的成本实现Android、iOS和Web的复用,也可以冠冕堂皇的突破苹果对热更新的封锁。 然而便...

    美团技术团队
  • Python多进程并行编程实践-mpi4py的使用

    專 欄 ❈PytLab,Python 中文社区专栏作者。主要从事科学计算与高性能计算领域的应用,主要语言为Python,C,C++。熟悉数值算法(最优化方法,...

    Python中文社区
  • JAVA中线程同步的方法(7种)汇总

    同步的方法: 一、同步方法   即有synchronized关键字修饰的方法。 由于java的每个对象都有一个内置锁,当用此关键字修饰方法时, 内置锁会保护整个...

    范蠡
  • 同样是追星 ,他们是这样做的 。

    最近我朋友疯狂迷恋韩国的偶像团体防弹少年团,于是拜托我帮忙写一段程序实时检测韩国新闻网站instiz旗下两个板块pt和clip,当出现自家idol的新闻时,程序...

    小小詹同学
  • Simple RNN时间序列预测

    首先分析一下,假设我们一次输入50个点,batch设为1,每个点就一个值,所以input的shape就是[50, 1, 1],这里我们换一种表示形式,把batc...

    mathor

扫码关注云+社区

领取腾讯云代金券