1. Sequential queue (loop)

Array-based loop queues are simple, resetting the queue entry and queue exit positions to the head of the array when the array is full.

public class CircleQueue<E> {
	
    // Object saves E because E cannot be E[] --> (E)obj
    private Object[] items;
    private int putIdx; // The actual team position
    private int takeIdx; // The actual queue position
    private int count; The size of the queue does not change after the array is initialized
	
	// Specify capacity initialization
    public CircleQueue(int size) {
        this.items = new Object[size];
        this.count = 0;
        this.putIdx = 0;
        this.takeIdx = 0;
    }
	
    public boolean enqueue(E e) {
        // Return when it is full
        if (count == items.length)  return false;
        / / in the
        items[putIdx] = e;
        PutIdx (++)
        // If putIdx reaches the last element of the array, it returns to 0
        if (++putIdx == items.length) putIdx = 0;
        count++;

        return true;
    }

    public E dequeue(a) {
    	// Return null if the queue is empty
        if (count == 0) return null;
        E res = (E) items[takeIdx];
        TakeIdx (++); takeIdx (++);
        // If takeIdx reaches the last element of the array, it returns to 0
        if (++takeIdx == items.length) takeIdx = 0;
        count--;
        return res;
    }

    public E peek(a) {
    	// Be careful not to make null judgments
        return count == 0 ? null: (E)items[takeIdx]; }}Copy the code

2. Chain queue

Before looking at the code, note a few non-null judgments:

  • An empty queue can be determined if:
    • head = null
    • tail = null
    • head = tail = null
  • Non-empty judgment required when entering/leaving the team:
    • Enqueue: tail = head = node if empty
    • Dequeue
      • Empty before queue exit: return null
      • Tail = head = null
public class LinkedQueue<E> {

    class Node<E> {
        E item;
        Node<E> next;

        public Node(E e) {
            this.item = e; }}private Node head; / / team first
    private Node tail; / / of the

    public LinkedQueue(a) {
    	// Head = tail = null when queue is empty
        head = tail = null; 
    }
	
    public void enqueue(E e) {
        Node node = new Node(e);
		
        // The queue is empty
        if(tail == null) {
            head = tail = node;
        }else{ tail.next = node; tail = node; }}public E dequeue(a) {
        // The queue is empty
        if (head == null) {
            return null;
        }
        E item = (E)head.item;
        // The queue is empty
        if (head.next == null) {
            head = tail = null;
        }
        return item;
    }

    public E peek(a) {
        return this.head == null ? null : (E)this.head.item; }}Copy the code

LinkedList is also an implementation of Queue. For more details, please refer to LinkedList source code analysis.