05 |队列

一、什么是队列？

队列是一种“操作受限”的线性表，只允许在一端插入和另一端输出。
队列和栈都是操作受限的线性表，区别在于栈是一头操作的，先进后出，后进先出，队列是尾部进入，头部输出。

队列的概念很好理解，基本操作也很容易掌握。作为一种非常基础的数据结构，队列的应用也非常广泛，特别是一些具有某些额外特性的队列，比如循环队列、阻塞队列、并发队列。它们在很多偏底层系统、框架、中间件的开发中，起着关键性的作用。比如高性能队列 Disruptor、Linux 环形缓存，都用到了循环并发队列；Java concurrent 并发包利用 ArrayBlockingQueue 来实现公平锁等。

二、队列的类型

1.顺序队列

用数组实现的队列叫作顺序队列

//大佬写的代码
// 用数组实现的队列
public class ArrayQueue {
   
     
  // 数组：items，数组大小：n
  private String[] items;
  private int n = 0;
  // head表示队头下标，tail表示队尾下标
  private int head = 0;
  private int tail = 0;

  // 申请一个大小为capacity的数组
  public ArrayQueue(int capacity) {
   
     
    items = new String[capacity];
    n = capacity;
  }

  // 入队
  public boolean enqueue(String item) {
   
     
    // 如果tail == n 表示队列已经满了
    if (tail == n) return false;
    items[tail] = item;
    ++tail;
    return true;
  }

  // 出队
  public String dequeue() {
   
     
    // 如果head == tail 表示队列为空
    if (head == tail) return null;
    // 为了让其他语言的同学看的更加明确，把--操作放到单独一行来写了
    String ret = items[head];
    ++head;
    return ret;
  }
}

//他自己优化的代码
   // 入队操作，将item放入队尾
  public boolean enqueue(String item) {
   
     
    // tail == n表示队列末尾没有空间了
    if (tail == n) {
   
     
      // tail ==n && head==0，表示整个队列都占满了
      if (head == 0) return false;
      // 数据搬移
      for (int i = head; i < tail; ++i) {
   
     
        items[i-head] = items[i];
      }
      // 搬移完之后重新更新head和tail
      tail -= head;
      head = 0;
    }
    
    items[tail] = item;
    ++tail;
    return true;
  }