算法通关村番外篇-数组实现队列

大家好我是苏麟 , 今天来用数组实现一下队列 .

数组实现队列

顺序存储结构存储的队列称为顺序队列，内部使用一个一维数组存储，用一个队头指针 front 指向队列头部节点(即使用int类型front来表示队头元素的下标)，用一个队尾指针rear(有的地方会用tail，只要在一个问题里统一起来就行了)，指向队列尾部元素(int类型rear来表示队尾节点的下标)。

初始化队列时: front = rear = -1(非必须，也可设置初始值为0，在实现方法时具体修改

队列满时: rear = maxSize - 1 (其中maxSize为初始化队列时，设置的队列最大元素个数)

队列为空时: front = rear

在代码中初始化了一个大小为6的顺序队列

其中 front 和 rear 指向的虚线框实际并不存在，仅用来表示初始化时的默认状态，因为我们实现的队列元素使用int存储元素，所以初始值均为 0(如用Objecl或范型则初始值为null)，执行queue.add(1) 到queue.add(6)方 法后队列的状态如下图:

接下来看下队列的出队情况，当第一次执行queue.pop0方法后，队列元素如上图所示，此时队列剩下5个元素:

?当第六次执行queue.pop0方法后，队列元素如下图所示 :

此时队列中元素已全部出队，按正常逻辑应该可以添加元素到队列中，但此时添加元素却会报队列已满错误(rear=maxSize-1)，当然即使前面元素未出队也会报相同错误。这就是我们常说的“假溢出”问题。为解决这个问题，就引出了我们的环形队列。?

代码实现

/**
 * 队列
 */
public class ArrayQueue {
    //队列存放的数据
    private int[] data;
    //队列大小
    private int maxSize;
    //队列头指针
    private int front;
    //队列尾指针
    private int rear;

    public ArrayQueue(int maxSize) {
        data = new int[maxSize];
        this.maxSize = maxSize;
        front = -1;
        rear = -1;
    }

    //判断队列是否满了
    public boolean isFull() {
        return rear == maxSize - 1;
    }

    //判断是否为空
    public boolean isEmpty() {
        return front == rear;
    }

    //添加数据
    public void add(int n) {
        if (isFull()) {
            System.out.println("队列已满!");
            return;
        }
        data[++rear] = n;
    }

    //删除数据
    public int pop() {
        if (isEmpty()) {
            throw new RuntimeException("队列为空 , 请先添加数据!");
        }
        int temp = data[++front];
        data[front] = 0;
        return temp;
    }

    //显示头部数据
    public void head() {
        if (isEmpty()) {
            throw new RuntimeException("队列为空 , 请先添加数据!");
        }
        System.out.println(data[front + 1]);
    }

    //打印全部数据
    public void forEach() {
        if (isEmpty()) {
            System.out.println("队列为空 , 请先添加数据!");
        }
        for (int i = front + 1; i <= rear; i++) {
            System.out.print(data[i] + " ");
        }
    }
}

这期就到这里 , 下期见!