数组实现队列

概述

队列，又称为伫列（queue），计算机科学中的一种抽象资料型别，是先进先出（FIFO, First-In-First-Out）的线性表。在具体应用中通常用链表或者数组来实现。队列只允许在后端（称为rear）进行插入操作，在前端（称为front）进行删除操作。

从上述的概念中我们可得知，队列两个主要的操作为入队(enqueue)与出队(dequeue)，入队为从队尾插入元素，出队为从队首去删除元素。

数组实现队列

数组实现的队列即元素容器为数组，为了完成入队与出队列的操作，同时还需要两个指针来标记队首和队尾。

代码实现

public class ArrayQueueTest {

    private final int[] items;
    /**
     * front 队首指针
     * rear 对尾指针
     * capital 队列容量
     */
    private int front, rear, capital;

    public ArrayQueueTest(Integer capital) {
        this.items = new int[capital];
        this.capital = capital;
        this.front = rear = 0;
    }

    /**
     * 从队尾插入元素
     *
     * @param item 元素
     */
    public void add(int item) {
        // 当前容量已满
        if (rear == capital) {
            if (front == 0) {
                throw new RuntimeException("队列已满");
            } else {
                // 所有元素向前移动一位
                for (int i = 0; i < items.length - 1; i++) {
                    items[i] = items[i + 1];
                }
                // 队尾指针向前移动一位，同时队首指针向前移动一位
                rear--;
                front--;
            }
        }
        items[rear] = item;
        rear++;
    }

    /**
     * 从队首取出元素
     *
     * @return 队首取出的元素
     */
    public int remove() {
        if (front == capital) {
            throw new RuntimeException("队列为空");
        }
        int item = items[front];
        front++;
        return item;
    }

    /**
     * 获取队列所有元素
     *
     * @return 队列所有元素数组
     */
    public int[] getItems() {
        int[] outItems = new int[rear - front];
        for (int i = 0; i < outItems.length; i++) {
            outItems[i] = items[front + i];
        }
        return outItems;
    }

    public static void main(String[] args) {
        ArrayQueueTest arrayQueue = new ArrayQueueTest(5);
        arrayQueue.add(1);
        arrayQueue.add(2);
        arrayQueue.add(3);
        arrayQueue.add(4);
        arrayQueue.add(5);
        System.out.println(Arrays.toString(arrayQueue.getItems()));

        for (int i = 0; i < 5; i++) {
            int removeItem = arrayQueue.remove();
            System.out.println(removeItem);
            System.out.println(Arrays.toString(arrayQueue.getItems()));
        }
        arrayQueue.add(8);
        System.out.println(Arrays.toString(arrayQueue.getItems()));
        arrayQueue.add(9);
        System.out.println(Arrays.toString(arrayQueue.getItems()));

//        for (int i = 10; i < 20; i++) {
//            arrayQueue.add(i);
//            System.out.println(Arrays.toString(arrayQueue.getItems()));
//        }
//        for (int i = 0; i < 10; i++) {
//            System.out.println(arrayQueue.remove());
//            System.out.println(Arrays.toString(arrayQueue.getItems()));
//        }
    }
}