队列（java实现）

队列也是一种操作受限的线性表。只能在队尾进行插入，队首进行删除，实现先进先出（FIFO）。

链表队列

链表队列.png

在初始状态下（即空队列），首/尾指针同时指向头节点，此时队列长度为0。

空队列.png

在队列中插入节点，将节点接入原列表，移动尾指针指向新的表尾节点即可。

插入队列.png

从队列中删除节点，即取出首指针指向的节点 并将其从队列中取出，首指针指向其原来指向的节点的下一个节点；当新的队首节点为空时，需修改队尾指针指向队首，使得队列为空队列。

出队列.png

/**
 * queue
 * @param <T> element type
 */
public class Queue<T> {
    //front pointer: always point to the head of queue
    QueueNode<T> front;
    //rear pointer: always point to the tail of queue
    QueueNode<T> rear;
    //queue head
    QueueNode<T> head;

    /**
     * constructor.
     */
    public Queue() {
        // create empty queue. front and rear both point to head.
        front = rear = head = new QueueNode<>();
    }

    /**
     * if it is an empty queue.
     * @return <code>true</code> if front and rear both point to head
     */
    public boolean isEmpty() {
        return front == head && rear == head;
    }

    /**
     * put element into queue.
     * @param data data needs to input into queue
     */
    public void enQueue(T data) {
        QueueNode<T> newNode = new QueueNode<>();
        newNode.data = data;
        rear.next = newNode;
        rear = newNode;
    }

    /**
     * pull out element from queue.
     * @return element
     */
    public QueueNode<T> deQueue() {
        QueueNode result = null;
        if (!this.isEmpty()) {
            result = front.next;
            QueueNode<T> newHead = result.next;
            //if it is the last element in queue, after pull out, set the queue to be empty
            if (newHead == null) {
                rear = front;
            }
            front.next = newHead;
        }
        return result;
    }

    /**
     * number of elements in queue.
     * @return size of queue
     */
    public int getQueueSize() {
        int size = 0;
        if (!this.isEmpty()) {
            QueueNode<T> current = front;
            while (current != rear) {
                current = current.next;
                size++;
            }
        }
        return size;
    }

    /**
     * clear queue.
     */
    public void clear() {
        //set queue at the status of initiation
        front = rear = head;
        head.next = null;
    }

    public static void main(String[] args) {
        Queue<String> queue = new Queue<>();
        queue.enQueue("a");
        queue.enQueue("b");
        System.out.println(queue.getQueueSize());
        System.out.println(queue.deQueue().data);
        System.out.println(queue.isEmpty());
        System.out.println(queue.getQueueSize());

    }
}

class QueueNode<T> {
    T data;
    QueueNode next;
}

循环队列
链表队列虽然用起来很方便，但是对于他的结构而言，除单纯存储数据以外，每个节点都还额外需要一个指针域来指明它的后继。 在内存限制要求较高的情况下，相对于链表队列，循环队列更节省空间。循环队列主要以顺序存储表结构来实现，省去指针域。

循环队列.png

此时我们引入一个哨兵占位用以 表示队列是否满，如不设置哨兵位，仅用front == rear判断是否位空/满时，难以分辨；在这种情况下rear + 1 mod capability == front 则说明队列存储空间满，rear == front时队列空

/**
 * circular queue.
 * @param <T> element type
 */
public class CircularQueue<T> {
    T[] elements;
    int front;
    int rear;
    // max size
    private final int CAPABILITY = 7;

    /**
     * constructor.
     * create an empty queue.
     */
    public CircularQueue() {
        elements = (T[]) new Object[CAPABILITY];
        front = rear = 0;
    }

    /**
     * identify if queue is full.
     * @return <code>true</code> if full
     */
    public boolean isFull() {
        // +1 for placeholder
        return (rear + 1) % CAPABILITY == front;
    }

    /**
     * identify if queue is empty
     * @return
     */
    public boolean isEmpty() {
        return rear == front;
    }

    /**
     * put element into queue.
     * @param data data
     * @return <code>true</code> if success
     */
    public boolean enQueue(T data) {
        if (!this.isFull()) {
            elements[rear] = data;
            rear++;
            return true;
        }
        return false;
    }

    /**
     * pull element from queue
     * @return data
     */
    public T deQueue() {
        if(!this.isEmpty()) {
            T result = elements[front];
            front++;
            return result;
        }
        return null;
    }

    public int getSize() {
        return (rear - front + CAPABILITY) % CAPABILITY;
    }

    public static void main(String[] args) {
        CircularQueue<String> queue = new CircularQueue<>();
        queue.enQueue("a");
        queue.enQueue("b");
        queue.enQueue("c");
        queue.enQueue("d");
        queue.enQueue("e");
        queue.enQueue("f");
        System.out.println(queue.enQueue("g"));

        System.out.println(queue.deQueue());
        System.out.println(queue.enQueue("g"));
        System.out.println(queue.deQueue());

        System.out.println(queue.getSize());
    }
}