数组实现队列和循环队列(Java)

如何理解“队列”

• 操作受限的线性表数据结构：先进先出
• 最基本的操作：入队和出队
• 队列分为队头和队尾，在队尾插入数据（入队），在队头删除数据（出队）。

用数组实现的顺序队列

• 思路：使用两个指针，一个head指针指向队头，一个tail指针指向队尾。
• 代码?

// 用数组实现的队列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; }}

• 代码存在问题：随着不停地进行入队、出队操作，head 和 tail 都会持续往后移动。当 tail 移动到最右边，即使数组中还有空闲空间，也无法继续往队列中添加数据了。
• 代码优化思路：在tail移动到最右边时，判断head是否为0，如果是0，说明队列已满，如果不是，说明队列未满，此时进行一次队列的迁移，队列从head到tail整体迁移到从0开始。
• 优化代码

// 入队操作，将 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;
  }

使用循环队列避免数据搬移操作

• 顾名思义，就是对队列的收尾是连接的，并不是真的像循环链表一样首尾连接，而是有相同的效果。
• 使用数组实现思路：数组实现队列，就是通过两个链表来访问数组，实现先进先出的效果。所以在入队和出队时，把控好数组的下标的变换即可实现循环队列的效果。所以需要了解判断队满的情况指针变换的情况。
• 思考：队列长度为n队满的情况（针对队尾）：循环队列不能再使用tail等于n来判断是否有队满的可能。此时，因为是循环队列，由于其循环进行入队和出队的操作的特殊性，当队满时，队列就是全部被填满的，所以此时，出队和入队指针指向的值的和为n-1.（也可以用表达式(tail+1)%n==head）队空的情况（针对队头）：不变，依然是head == tail时为队空。指针变换的思考：不考虑队满和队空时，head和tail指针需要在等于n-1时，下一次变换为0.所以，可以使用一个判断或者使用+1整除n。
• 代码

public class CircularQueue {
  // 数组：items，数组大小：n
  private String[] items;
  private int n = 0;
  // head 表示队头下标，tail 表示队尾下标
  private int head = 0;
  private int tail = 0;

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

  // 入队
  public boolean enqueue(String item) {
    // 队列满了
    if (tail + head + 1 == n) return false;
    items[tail] = item;
    tail = (tail + 1) % n;
    return true;
  }

  // 出队
  public String dequeue() {
    // 如果 head == tail 表示队列为空
    if (head == tail) return null;
    String ret = items[head];
    head = (head + 1) % n;
    return ret;
  }
}