队列的特点和使用场景

2020-10-10  本文已影响0人  文景大大

前言

本篇文章主要解决如下的问题：

  1. 队列的特点是什么？
  2. 如何实现一个队列？
  3. 在什么场景下需要使用循环队列？
  4. 阻塞队列的特点和使用场景？
  5. 并发队列的特点是什么？
  6. 队列的具体使用场景有哪些？

一、队列的定义

和栈一样也是一种操作受限的线性表，特点是元素先进先出，比较适用于需要排队获取资源的业务场景中。和栈的不同是，栈的入栈和出栈操作都是在栈顶进行的，而队列的入队操作是在队尾进行，出队操作是在队头进行。

二、实现一个队列

2.1 顺序队列

用数组实现的队列称为顺序队列，一个基本的实现如下所示：

public class MyQueue {

    private String[] items;
    private int size = 0;
    // 头指针
    private int head = 0;
    // 尾指针
    private int tail = 0;

    public MyQueue(int size){
        this.items = new String[size];
        this.size = size;
    }

    public boolean enqueue(String item){
        // 队列已满
        if(tail == size){
            return false;
        }

        items[tail] = item;
        tail++;
        return true;
    }

    public String dequeue(){
        // 队列已空
        if(head == tail){
            return null;
        }

        String result = items[head];
        head++;
        return result;
    }

}
顺序队列1 顺序队列2

当入队和出队一定次数后，我们发现队列的头尾指针不断地逼近数组后半部分，到最后，即使数组中还有空闲空间，也不能再入队了，如何解决这一问题呢？

其实和数组一样，当检测元素入队的时候，数组中明明有空闲的空间，但是当前没有空间可以入队时，需要做一次数据搬移操作。修改后的入队代码修改为如下：

public boolean enqueue(String item){
        if(tail == size){
            // 队列已满
            if(head == 0){
                return false;
            }
            // 队列内容整体搬移到数组头部
            for(int i=head;i<tail;i++){
                items[i-head] = items[i];
            }
            tail -= head;
            head = 0;
        }

        items[tail] = item;
        tail++;
        return true;
    }
顺序队列的数据搬移

2.2 链式队列

用链表实现的队列称为链式队列，相较于顺序队列，链式队列不需要连续的内存空间，也不需要搬移数据，比较适合入队和出队操作，但是不方便查找队列中的元素。

2.3 循环队列

循环队列主要是为了解决顺序队列中数据搬移的问题，它把数组的最后一个空间和第一个空间衔接起来，形成一个环，当tail在最后一个空间时，此时如果再入队，那么tail就会变成0，随后变成1、2、3等，如此循环。

链式队列1 链式队列2

需要注意的，此时判断队列为空的条件还是head == tail，但是判断队列已满的条件则是(tail+1)%size==head，可以自己画图总结下规律就能得到如上答案。

2.4 阻塞队列

在队列的基础上增加了阻塞的操作。即在队列为空的时候，如果有线程从队列中取数据，那么该线程会被阻塞，一直等到队列中有了数据，才会唤醒该线程，取得它需要的数据；在队列为满的时候，如果有线程需要将数据放入队列，那么也会被阻塞，一直等到队列中存在空闲空间时，才会唤醒该线程，放入元素。

阻塞队列的优势在于，可以控制消费者或者生产者的速率，还可以通过调整消费者和生产者的数量来提高处理速度。

阻塞队列

2.5 并发队列

线程安全的队列我们称为并发队列，比如我们可以在入队和出队的方法上加上同步锁，保证同一时刻只有一个出队操作或者入队操作。当然，加锁的粒度比较粗，效率低下，我们可以在循环队列上使用CAS原子操作来实现非常高效的并发队列（无锁并发队列）。

三、队列的使用场景

3.1 Disruptor

3.2 Linux环形缓存

3.3 ArrayBlockingQueue

3.4 池资源

诸如线程池、数据库连接池之类的池资源都会使用到队列。比如，当池子中没有空闲资源的时候，新的线程任务还去池子中请求资源该怎么办？通常有如下两种策略：

上一篇下一篇

猜你喜欢

热点阅读