链表

注意

• 本文来自 极客时间 王争的课程

数组实现队列

思想

• head 表示队头下标，tail 表示队尾下标，开始都为0

• 随着不停地进行入队、出队操作，head 和 tail 都会持续往后移动

  
  image.png

• tail 移动到最右边，即使数组中还有空闲空间，也无法继续往队列中添加数据了；移动数据解决

• 出队不用移动数据，入队处理即可

代码实现

 // 用数组实现的队列
  public class DynamicArrayQueue {
    // 数组：items，数组大小：n
    private String[] items;
    private int n = 0;
    // head 表示队头下标，tail 表示队尾下标
    private int head = 0;
    private int tail = 0;
  
    // 申请一个大小为 capacity 的数组
    public DynamicArrayQueue(int capacity) {
      items = new String[capacity];
      n = capacity;
    }
  
      // 入队操作，将 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;
    }
  
  
    // 出队
    public String dequeue() {
      // 如果 head == tail 表示队列为空
      if (head == tail) return null;
      // 为了让其他语言的同学看的更加明确，把 -- 操作放到单独一行来写了
      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();
    }
  }

链表实现队列

/**
 * 基于链表实现的队列
 *
 * Author: Zheng
 */
public class QueueBasedOnLinkedList {

  // 队列的队首和队尾
  private Node head = null;
  private Node tail = null;

  // 入队
  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;
    }
  }

  // 出队
  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;
    }
  }

}

循环链表

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 + 1) % n == head) 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;
  }
}