本文共 3665 字，大约阅读时间需要 12 分钟。

数据结构和算法系列共八篇

1.什么是队列

队列其实也是特殊的线性表。被限制了从尾插入数据，从头取出数据

特点：

• 先进后先出 FIFO (First In First Out)
• 向队尾(rear)插入元素称为入队
• 从队首(front)中删除元素称为出队

常见操作

• size: 大小
• isEmpty: 是否为空
• enqueue: 入队
• dequeue: 出队
• peek 取队首元素

2.存储结构

• 顺序队列结构
• 链队列结构

2-1.顺序队列

缺点：

• 从队首移除数据(出队)，空间浪费了。

那如何解决呢？

可以使用循环顺序方式。末尾元素的下一个指向头元素。

循环顺序队列实现

public class CircleArrayQueue
   
     {
       private Object[] elementData;    private int size = 0;    private int front = 0;    private int rear = 0;    private ReentrantLock lock = new ReentrantLock();    private Condition fullCondition = lock.newCondition();    private Condition emptyCondition = lock.newCondition();    public CircleArrayQueue(int size) {
           this.size = size;        elementData = new Object[size];        front = 0;        rear = 0;    }    public void enqueue(T value) {
           try {
               lock.lock();            if (isFull()) {
                   System.out.println("队列满了，还往哪塞？" + value);                fullCondition.await();            }            this.elementData[rear] = value;            //rear+1，防止超过size，要跟size取模            rear = (rear + 1) % size;            emptyCondition.signal();        } catch (InterruptedException e) {
               e.printStackTrace();        } finally {
               lock.unlock();        }    }    public T dequeue() {
           try {
               lock.lock();            if (isEmpty()) {
                   System.out.println("队列空了，还取个啥子？");                emptyCondition.await();            }            T value = (T) this.elementData[front];            //front+1，防止超过size，要跟size取模            front = (front + 1) % size;            fullCondition.signal();            return value;        } catch (InterruptedException e) {
               e.printStackTrace();        } finally {
               lock.unlock();        }        return null;    }    public int size() {
           return Math.abs(rear - front);    }    public boolean isEmpty() {
           // front和rear在一起说明是空        return this.front == this.rear;    }    public boolean isFull() {
           // 下表从0开始，rear+1 取mod跟front对比        return (this.rear + 1) % this.size == front;    }}
   

测试

public class CircleArrayQueueTest {
       public static void main(String[] args) throws InterruptedException {
           final CircleArrayQueue
   
     queue = new CircleArrayQueue
    
     (5);        int totalCount = 20;        ExecutorService pool = Executors.newFixedThreadPool(2);        pool.submit(() -> {
               for (int i = 0; i < totalCount; i++) {
                   queue.enqueue("" + (Math.random() * 100));            }        });        pool.submit(() -> {
               for (int i = 0; i < totalCount; i++) {
                   System.out.println(queue.dequeue());            }        });        TimeUnit.SECONDS.sleep(5);        pool.shutdown();    }}
    
   

2-2.链队列

队列的链式存储可以使用单链表来实现。需要两个node，分别对应队首front和队尾rear

3.双端队列

当队列两端都可以操作，不限于一端读、一端写。两端都可以读写，那么就是双端队列了。

4.演示

我们直接使用java提供的类来演示

• Queue：队列类

Queue是接口，使用了LinkedList来实列化对象。因为LinkedList实现了Queue

Queue里有以下几个方法

public class JavaQueueTest {
       public static void main(String[] args) {
           Queue
   
     queue = new LinkedList
    
     ();        queue.offer("a");        queue.offer("b");        queue.offer("c");        queue.offer("d");        while (!queue.isEmpty()){
               System.out.print(queue.poll());        }    }}
    
   

结果：abcd

5.进入一步深造

下一步如何再深造呢?

去看java的Queue的实现类ListList、ConcurrentLinkedQueue等源码

6.推荐

能读到文章最后，首先得谢谢您对本文的肯定，你的肯定是对博主最大的鼓励。

你觉本文有帮助，那就点个👍

转载地址：http://zkhws.baihongyu.com/