Data Structure-2 Queue 循环队列，用数组实现

1. 队列基础

Queue. A queue supports the insert and remove operations using a first-in first-out (FIFO) discipline. By convention, we name the queue insert operation enqueue and the remove operation dequeue, as indicated in the following API.
队列：是一种支持FIFO(First in First out)的数据结构，一般有入队列和出队列2种基本操作，循环队列实现是对空间的有效利用。

2. 相关代码及说明

//Queue.java
package com.fqy.queue;

import java.lang.reflect.Array;

public class Queue<T> {
private int size;
private int total;
private int front;
private int rear;
private T[] queue;

    @SuppressWarnings("unchecked")
public Queue(int size) {
this.size = size;
        total = 0;
        front = 0;
        rear = 0;
        total = 0;
        queue = (T[]) new Object[this.size];
    }

// Why code like this? To produce 'generic' array
public Queue(Class<T[]> cl, int size) {
this.size = size;
        total = 0;
        front = 0;
        rear = 0;
        total = 0;
        queue = cl.cast(Array.newInstance(cl.getComponentType(), this.size));
    }

public boolean enqueue(T item) {
if (!isFull()) {
            queue[rear] = item;
// Special case
            rear = (rear + 1) % size;
            total++;
return true;
        } else {
return false;
        }
    }

public T dequeue() {
if (!isEmpty()) {
            T item = queue[front];
            queue[front] = null;
            front = (front + 1) % size;
            total--;

return item;
        } else
return null;
    }

public void traverseQueue() {
int index = front;
for (int i = 0; i < total; i++) {
            System.out.print(queue[index] + " ");
            index = (index + 1) % size;
        }
    }

/*
 * 在循环队列结构下，当front==rear时为空队列，当front==(rear+1)%maxSize时为满队列。
 * 注意，满队列时，仍有一个元素空间未被使用。若不留该空间，则队尾指针rear指向该空间导致了， 满队列和空队列判定条件相同。
 */
public boolean isFull() {
// return total == size;
return (rear + 1) % size == front;
    }

public boolean isEmpty() {
// return total == 0;
return rear == front;
    }

public int getTotal() {
return total;
    }
}


//TestQueue.java
package com.fqy.queue;

import java.util.Random;

public class TestQueue {

public static void main(String[] args) {
// The actual elements a queue can hold is 10-1;
        Queue<Integer> queue = new Queue<>(Integer[].class, 11);
        Random random = new Random();

for (int i = 0; i < 10; i++) {
int val = random.nextInt(100);
            System.out.print(val + " ");
            queue.enqueue(val);
        }
        System.out.println();
        queue.traverseQueue();
        System.out.println("\n" + queue.getTotal());
while (!queue.isEmpty()) {
            System.out.print(queue.dequeue() + " ");
        }
    }

}


//Running result:
48 55 95 82 31 5 18 80 25 92 
48 55 95 82 31 5 18 80 25 92 
10
48 55 95 82 31 5 18 80 25 92