队列实现系列（一）——队列的数组实现(Java版)

队列的原理见博客：队列（queue）原理

使用数组来实现队列时，如果用一般的方式实现，还是比较简单的。一般队列和循环队列的实现，只是在个别地方会有不同，我在代码里已经注释出，根据自己需要修改即可。

实现的操作：

1. 入队
2. 出队
3. 获取队首元素
4. 获取队列长度

辅助操作：

1. 判断队列是否为空；
2. 判断队列是否满；
3. 清空队列。

下面是数组循环队列的实现代码(ArrayQueue)

/**
 * Created by Hzc on 2019/1/28.
 * 队列的数组实现
 */
public class ArrayQueue<Type>{

    /**
     * MAXSIZE：队列最大长度
     * queue：队列数组
     * length：队列长度
     * head：队首索引
     * tail：队尾索引
     */
    private static final int MAXSIZE = 5;
    private Type[] queue;
    private int length;
    private int head;
    private int tail;

    /**
     * 数组队列的两种构造方法
     */
    public ArrayQueue(){//默认构造方法
        queue = (Type[]) new Object[MAXSIZE];
        head = tail = 0;
        length = 0;
    }

    public ArrayQueue(Type[] array){//根据给定数组构造队列
        this.queue = array;
        length = array.length;
        head = tail = 0;
    }

    /**
     * 数据入队
     * @param data：需要入队的数据
     * @return ：入队成功与否
     */
    public boolean enQueue(Type data) {
        if (isFull())//队满，则返回 false
            return false;
        queue[tail] = data;//队尾处放上数据
        tail = (tail + 1) % MAXSIZE;//将队尾移动到下一个位置
        //一般队列： tail = tail+1;
        length++;//队列长度递增 1
        return true;
    }

    /**
     * 数据出队
     * @return 出队的数据
     */
    public Type deQueue() {
        Type data;
        if (isEmpty())//队列为空
            return null;
        data = queue[head];//将当前队首数据记录下来
        head = (head+1)%MAXSIZE;//将队首移动到下一个位置
        //一般队列：head = head+1；
        length --;//将队列长度递减 1
        return data;
    }

    /**
     * 获取队首数据
     * @return 队首数据
     */
    public Type getQueueHead() {
        return queue[head];
    }

    /**
     * 获取队列长度
     * @return 队列长度
     */
    public int getLength() {
        return this.length;
    }

    /**
     * 判断队列是否为空
     * @return 队列是否为空
     */
    public boolean isEmpty(){
        if ((head == tail) && (queue[head]==null))//队首与队尾相同，且不存在元素，则队列空
            return true;
        return false;
    }

    /**
     * 判断队列是否满
     * @return 队列是否满
     */
    public boolean isFull() {
        if (head == (tail+1)%MAXSIZE)//队尾+1即为队首，则队列满
            //一般队列： if(tail == MAXSIZE)
            return true;
        return false;
    }

    /**
     * 清空队列
     */
    public void clear() {
        head = tail = length = 0;
        queue[head] = null;
    }

    /**
     * 这个方法仅用于打印，实际使用队列时，不会用到
     */
    public void display(){
        System.out.print("  从头到尾打印队列：");
        for (int i = head; i < MAXSIZE; i++) {
            if (i == tail)
                break;
            System.out.print(" " + queue[i]);
            if (i == MAXSIZE-1)
                i = -1;
        }
        System.out.println();
    }
}

下面是测试代码：

public class ArrayQueueTest {

    private static final int MULTI = 6;
    private static final int LENGTH = 20;
    private ArrayQueue<Integer> queue;

    public static void main(String[] args) {
        ArrayQueueTest a = new ArrayQueueTest();
        a.run();
    }

    public void run(){
        queue = new ArrayQueue();
        testEnQueue();//将队列填满
        testDeQueue();//让队首元素出队
        for (int i = 0; i < 3; i++) {//再添加几个数据
            if(!queue.enQueue(i*7)){
                System.out.println("队列满！");
                break;
            }
        }
        queue.display();
        testDeQueue();
        testDeQueue();//再出队两个元素
        testGetQueueHead();
        testGetLength();
        testClear();
    }

    public void testEnQueue(){
        System.out.println("----测试enQueue()----");
        for (int i = 0; i < LENGTH; i++) {
            if(!queue.enQueue(i*MULTI)) {
                System.out.println("队列满！");
                break;
            }
        }
        queue.display();
    }

    public void testDeQueue(){
        System.out.println("----测试deQueue()----");
        System.out.println("出队：" + queue.deQueue());
        queue.display();
    }

    public void testGetQueueHead(){
        System.out.println("----测试getQueueHead()----");
        System.out.println("当前队首：" + queue.getQueueHead());
        queue.display();
    }

    public void testGetLength(){
        System.out.println("----测试getLength()----");
        System.out.println("当前队列长度：" + queue.getLength());
        queue.display();
    }

    public void testClear(){
        System.out.println("----测试clear()----");
        queue.clear();
        queue.display();
    }
}

代码不够规范，还望多多包涵~/bq