1.链式队列和数组队列

---

(1)数组队列

    队列与栈的最大特点就是：队列有队头和队尾指针(下标)，而栈只有顶端指针(下标)。

    一句话总结两者特点：“队列吃多了会拉（头进尾出），而栈吃多了会吐 （头进头出）”

public class ArrayQueue {
  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移动到最右边，即使数组中还有空闲空间，也无法继续往队列中添加数据。