注意

• 本文來(lái)自 極客時(shí)間 王爭(zhēng)的課程

數(shù)組實(shí)現(xiàn)隊(duì)列

思想

• head 表示隊(duì)頭下標(biāo)，tail 表示隊(duì)尾下標(biāo)，開(kāi)始都為0

• 隨著不停地進(jìn)行入隊(duì)、出隊(duì)操作，head 和 tail 都會(huì)持續(xù)往后移動(dòng)

  
  
  image.png

• tail 移動(dòng)到最右邊，即使數(shù)組中還有空閑空間，也無(wú)法繼續(xù)往隊(duì)列中添加數(shù)據(jù)了；移動(dòng)數(shù)據(jù)解決

• 出隊(duì)不用移動(dòng)數(shù)據(jù)，入隊(duì)處理即可

代碼實(shí)現(xiàn)

 // 用數(shù)組實(shí)現(xiàn)的隊(duì)列
  public class DynamicArrayQueue {
    // 數(shù)組：items，數(shù)組大?。簄
    private String[] items;
    private int n = 0;
    // head 表示隊(duì)頭下標(biāo)，tail 表示隊(duì)尾下標(biāo)
    private int head = 0;
    private int tail = 0;
  
    // 申請(qǐng)一個(gè)大小為 capacity 的數(shù)組
    public DynamicArrayQueue(int capacity) {
      items = new String[capacity];
      n = capacity;
    }
  
      // 入隊(duì)操作，將 item 放入隊(duì)尾
    public boolean enqueue(String item) {
      // tail == n 表示隊(duì)列末尾沒(méi)有空間了
      if (tail == n) {
        // tail ==n && head==0，表示整個(gè)隊(duì)列都占滿了
        if (head == 0) return false;
        // 數(shù)據(jù)搬移
        for (int i = head; i < tail; ++i) {
          items[i-head] = items[i];
        }
        // 搬移完之后重新更新 head 和 tail
        tail -= head;
        head = 0;
      }
      
      items[tail] = item;
      ++tail;
      return true;
    }
  
  
    // 出隊(duì)
    public String dequeue() {
      // 如果 head == tail 表示隊(duì)列為空
      if (head == tail) return null;
      // 為了讓其他語(yǔ)言的同學(xué)看的更加明確，把 -- 操作放到單獨(dú)一行來(lái)寫(xiě)了
      String ret = items[head];
      ++head;
      return ret;
    }
    
     public void printAll() {
      for (int i = head; i < tail; ++i) {
        System.out.print(items[i] + " ");
      }
      System.out.println();
    }
  }

鏈表實(shí)現(xiàn)隊(duì)列

/**
 * 基于鏈表實(shí)現(xiàn)的隊(duì)列
 *
 * Author: Zheng
 */
public class QueueBasedOnLinkedList {

  // 隊(duì)列的隊(duì)首和隊(duì)尾
  private Node head = null;
  private Node tail = null;

  // 入隊(duì)
  public void enqueue(String value) {
    if (tail == null) {
      Node newNode = new Node(value, null);
      head = newNode;
      tail = newNode;
    } else {
      tail.next = new Node(value, null);
      tail = tail.next;
    }
  }

  // 出隊(duì)
  public String dequeue() {
    if (head == null) return null;

    String value = head.data;
    head = head.next;
    if (head == null) {
      tail = null;
    }
    return value;
  }

  public void printAll() {
    Node p = head;
    while (p != null) {
      System.out.print(p.data + " ");
      p = p.next;
    }
    System.out.println();
  }

  private static class Node {
    private String data;
    private Node next;

    public Node(String data, Node next) {
      this.data = data;
      this.next = next;
    }

    public String getData() {
      return data;
    }
  }

}

循環(huán)鏈表

public class CircularQueue {
  // 數(shù)組：items，數(shù)組大?。簄
  private String[] items;
  private int n = 0;
  // head 表示隊(duì)頭下標(biāo)，tail 表示隊(duì)尾下標(biāo)
  private int head = 0;
  private int tail = 0;

  // 申請(qǐng)一個(gè)大小為 capacity 的數(shù)組
  public CircularQueue(int capacity) {
    items = new String[capacity];
    n = capacity;
  }

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

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