资讯专栏INFORMATION COLUMN

我理解的数据结构(三)—— 队列(Queue)

hlcc / 2911人阅读

摘要:我理解的数据结构三队列一队列队列是一种线性结构相比数组,队列对应的操作是数组的子集只能从一端队尾添加元素,只能从另一端队首取出元素队列是一种先进先出的数据结构二数组队列与循环队列数组队列如果你有看过我之前的文章不要小看了数组或者栈,你就会发

我理解的数据结构(三)—— 队列(Queue) 一、队列

队列是一种线性结构

相比数组,队列对应的操作是数组的子集

只能从一端(队尾)添加元素,只能从另一端(队首)取出元素

队列是一种先进先出的数据结构(FIFO)

二、数组队列与循环队列 1. 数组队列
如果你有看过我之前的文章不要小看了数组或者栈,你就会发现,自己封装一个数组队列是如此的轻松加愉快!

(1)先定义一个接口,接口中定义队列需要实现的方法

public interface Queue {
    int getSize();
    boolean isEmpty();
    // 查看队首元素
    E getFront();
    // 入队
    void enqueue(E ele);
    // 出队
    E dequeue();
}

(2)实现数组队列

public class ArrayQueue implements Queue {
    
    // 这里的数组是在之前的文章中封装好的,直接拿来用就好了
    private ArrayNew array;

    public ArrayQueue(int capacity) {
        array = new ArrayNew<>(capacity);
    }

    public ArrayQueue() {
        this(10);
    }

    public int getCapacity() {
        return array.getCapacity();
    }

    @Override
    public int getSize() {
        return array.getSize();
    }

    @Override
    public boolean isEmpty() {
        return array.isEmpty();
    }

    @Override
    public E getFront() {
        return array.getFirst();
    }

    @Override
    public void enqueue(E ele) {
        array.addLast(ele);
    }

    @Override
    public E dequeue() {
        return array.removeFirst();
    }

    @Override
    public String toString() {

        StringBuffer res = new StringBuffer();

        res.append(String.format("arrayQueue: size = %d, capacity = %d
", getSize(), getCapacity()));
        res.append("front [");

        for (int i = 0; i < array.getSize(); i++) {
            res.append(array.get(i));
            if (i != getSize() - 1) {
                res.append(", ");
            }
        }
        res.append("] tail");
        return res.toString();

    }

}

(3)数组队列的复杂度

方法 复杂度
enqueue O(1) 均摊
dequeue O(n)
front O(1)
getSize O(1)
isEmpty O(1)
这个时候我们会发现,在进行出队操作的时候,数组队列的复杂度是0(n),如果我们频繁的进行出队操作,那么其实数组队列的效率是很低的,如何提升数组队列的性能呢?这个时候我们就要用到循环队列了。
2. 循环队列队列
循环队列的原理:

dequeue时,不要在去除队首元素时,把整体向前移动

维护 fronttailsize 这三个属性

enqueue的时候tail++

dequeue的时候front++

(1)实现循环队列

public class LoopQueue implements Queue {

    private E[] array;
    private int size;
    private int front;
    private int tail;

    public LoopQueue(int capacity) {
        // 我们需要浪费一个空间去判断队列是否已满,所以需要把capacity + 1
        array = (E[])new Object[capacity + 1];
        front = 0;
        tail = 0;
        size = 0;
    }

    public LoopQueue() {
        this(10);
    }

    // 返回用户传递的队列大小
    public int getCapacity() {
        return array.length - 1;
    }

    @Override
    public int getSize() {
        return size;
    }

    @Override
    public boolean isEmpty() {
        return front == tail;
    }

    @Override
    public E getFront() {
        if (isEmpty()) {
            throw new IllegalArgumentException("Queue is empty. Can"t get front.");
        }

        return array[0];
    }

    @Override
    public void enqueue(E ele) {

        if (front == (tail + 1) % array.length) {
            // 扩展队列长度为原长度2倍
            resize(getCapacity() * 2);
        }

        array[tail] = ele;
        size++;
        tail = (tail + 1) % array.length;
    }

    @Override
    public E dequeue() {

        if (isEmpty()) { // 队列为空
            throw new IllegalArgumentException("Queue is empty. Can"t get dequeue.");
        }

        E ele = array[front];

        size--;
        array[front] = null;
        front = (front + 1) % array.length;

        if (size == getCapacity() / 4 && getCapacity() / 2 != 0) {
            resize(getCapacity() / 2);
        }

        return ele;

    }

    private void resize(int newCapacity) {
        E[] newArray = (E[]) new Object[newCapacity + 1];

        for (int i = 0; i < size; i++) {
            newArray[i] = array[(front + i) % array.length];
        }

        array = newArray;
        front = 0;
        tail = size;
    }

    @Override
    public String toString() {
        StringBuffer res = new StringBuffer();

        res.append(String.format("queue: size = %d, capacity = %d
", getSize(), getCapacity()));
        res.append("front [");

        // 循环条件,和循环增量都要注意下
        for (int i = front; i != tail; i = (i + 1) % array.length) {
            res.append(array[i]);

            if ((i + 1) % array.length != tail) {
                res.append(", ");
            }
        }
        res.append("] tail");

        return res.toString();
    }

}

(2)循环队列的复杂度

方法 复杂度
enqueue O(1) 均摊
dequeue O(1) 均摊
front O(1)
getSize O(1)
isEmpty O(1)
三、用时间说话

(1)用时方法

public static double test(Queue q, int opCount) {

    // 纳秒
    long startTime = System.nanoTime();

    Random random = new Random();

    for (int i = 0; i < opCount; i++) {
        q.enqueue(random.nextInt(Integer.MAX_VALUE));
    }
    for (int i = 0; i < opCount; i++) {
        q.dequeue();
    }

    // 纳秒
    long endTime = System.nanoTime();

    return (endTime - startTime) / 1000000000.0;
}

(2)调用

// 十万次入队和十万次出队操作
int opCount = 100000;

ArrayQueue aq = new ArrayQueue<>();
double time1 = test(aq, opCount);
System.out.println(time1);

LoopQueue lq = new LoopQueue<>();
double time2 = test(lq, opCount);
System.out.println(time2);

(3)结果

14.635995113

0.054536447

这个就是算法和数据结构的力量!

文章版权归作者所有,未经允许请勿转载,若此文章存在违规行为,您可以联系管理员删除。

转载请注明本文地址:https://www.ucloud.cn/yun/29300.html

相关文章

  • 理解数据结构)—— 队列Queue

    摘要:我理解的数据结构三队列一队列队列是一种线性结构相比数组,队列对应的操作是数组的子集只能从一端队尾添加元素,只能从另一端队首取出元素队列是一种先进先出的数据结构二数组队列与循环队列数组队列如果你有看过我之前的文章不要小看了数组或者栈,你就会发 我理解的数据结构(三)—— 队列(Queue) 一、队列 队列是一种线性结构 相比数组,队列对应的操作是数组的子集 只能从一端(队尾)添加元素,...

    wean 评论0 收藏0
  • 消息中间件——RabbitMQ(理解RabbitMQ核心概念和AMQP协议!

    摘要:后续介绍交换机,生产者直接将消息投递到中。消息,服务器和应用程序之间传送的数据,由和组成。也称为消息队列,保存消息并将它们转发给消费者。主要是应为和有一个绑定的关系。 showImg(https://img-blog.csdnimg.cn/20190509221741422.gif); showImg(https://img-blog.csdnimg.cn/20190731191914...

    sihai 评论0 收藏0
  • 【Java实现】栈和队列就是这么简单

    摘要:一前言上一篇已经讲过了链表实现单向链表了,它跟数组都是线性结构的基础,本文主要讲解线性结构的应用栈和队列如果写错的地方希望大家能够多多体谅并指正哦,如果有更好的理解的方式也希望能够在评论下留言,让大家学习学习二数据结构栈就是这么简单数据结构 一、前言 上一篇已经讲过了链表【Java实现单向链表】了,它跟数组都是线性结构的基础,本文主要讲解线性结构的应用:栈和队列 如果写错的地方希望大家...

    Ethan815 评论0 收藏0
  • 学习JavaScript数据结构与算法(一):栈与队列

    摘要:之数组操作接下来就是数据结构的第一部分,栈。以字符串显示栈中所有内容方法的实现说明需要往栈中添加新元素,元素位置在队列的末尾。的前端乐园原文链接寒假前端学习学习数据结构与算法,栈与队列 本系列的第一篇文章: 学习JavaScript数据结构与算法(一),栈与队列第二篇文章:学习JavaScript数据结构与算法(二):链表第三篇文章:学习JavaScript数据结构与算法(三):集合第...

    Flink_China 评论0 收藏0
  • 学习数据结构与算法之栈与队列

    摘要:于是翻出了机房里的这本学习数据结构与算法开始学习程序员的基础知识。这本书用了我最熟悉的来实现各种数据结构和算法,而且书很薄,可以说是一本不错的入门教程。队列在头部删除元素,尾部添加元素。 本系列所有文章:第一篇文章:学习数据结构与算法之栈与队列第二篇文章:学习数据结构与算法之链表第三篇文章:学习数据结构与算法之集合第四篇文章:学习数据结构与算法之字典和散列表第五篇文章:学习数据结构与算...

    pingan8787 评论0 收藏0

发表评论

0条评论

hlcc

|高级讲师

TA的文章

阅读更多
最新活动
阅读需要支付1元查看
<