队列的顺序存储

队列的基本概念

队列（Queue）是具有一定操作约束的线性表，并且只能在一端插入，而在另一端删除。

数据插入被称为入队列（AddQ）。

数据删除被称为出队列（DeleteQ）。

如果将元素A、B、C、D依次插入队列，第一个从队列删除的元素将是A，即先插入的将率先被删除，因此队列是先来先服务，数据也是先进先出。

​​​​​例如排队就是队列问题。​

队列的抽象数据类型描述

• 类型名称：队列（Queue）
• 数据对象集：一个有0个或多个元素的有穷线性表。
• 操作集
  • 1、Queue CreateQueue(int MaxSize)：生成长度为MaxSize的空队列；
  • 2、int IsFullQ(Queue Q,int MaxSize)：判断队列Q是否已满；
  • 3、void AddQ(Queue Q,ElementType item)：将数据元素item插入到队列Q中；
  • 4、int IsEmptyQ(Queue Q)：判断队列Q是否为空；
  • 5、ElementType DeleteQ(Queue Q)：将队头数据元素从队列中删除并返回。

队列的顺序存储实现

​队列的顺序存储结构通常有一个一维数组和一个记录队列头元素位置的变量front以及一个记录队列伪元素的变量read组成。​front和rear加一个元素或删除一个元素都是加1。

思路：队列最简单的表示方法就是用数组。

用数组存储队列的方法有很多，一般可以选择将队列头放数组下标小的位置，而将队列尾放数组下标大的位置，并用两个变量front和rear分布指示队列的头和尾。一般front和rear先初始化为-1。当有元素入队，rear向右移动一格（即加1），放入队尾元素；当有元素出队，先将front向右移动一格（加1），再删除队头元素。

​​随着入队出队的进行，可能会出现“假溢出”的情况，为了解决队尾溢出而实际上数组仍有空余空间的问题，一般在队列的顺序存储结构中采用循环队列的方式：rear和front到达数组端点时，能折回到数组开始处，即相当于将数组头尾相接，成环状。当插入和删除操作的作用单元达到数组的末端后，用公式“rear（或front）%数组长度”取余运算就可以实现折返到起始单元。这就解决了假溢出问题。​

采用循环队列解决假溢出问题，当在循环队列中初始化，该如何根据front和rear值判断当前队列是空还是满？如果队列初始化时间front和rear都初始化为0，当插入一个元素时rear加1，删除一个元素时front加1，当front和rear相等时表示队列空（注意当队满的时候front和rear也会相等，所以有下面的方法）。

判断队列满还是空有两种解决方法：（1）增设一个变量，比如：记录当前队列元素个数的变量size，后者用一个变量flag记录最后一次操作是入队还是出队。根据变量size，就可以直接判断队列满还是空​​；根据变量flag就可以知道front等于rear时是满还是空。（2）是少用一个元素空间​，此时就是队尾指针加1就会赶上队头指针，因此队满的条件是：（rear+1）%数组长度等于front。队空的条件仍然是：rear等于front。

Java代码实现

/**
 * 队列的顺序存储
 *
 * @author lck100
 */
public class MyQueue {
    private int[] queue;// 一维数组（即队列）
    private int front;// 记录队列头元素位置
    private int rear;// 记录队列尾元素位置
    private int maxSize;// 队列最大容量

    private MyQueue(int maxSize) {
        // 分配数组空间
        queue = new int[maxSize];
        // 初始化变量
        this.maxSize = maxSize;
        // 将队列头和尾都初始化为0
        this.front = 0;
        this.rear = 0;
    }

    /**
     * 判断队列是否已满
     *
     * @return 如果已满返回true，否则返回false
     */
    public boolean isFull() {
        return (rear + 1) % maxSize == front;
    }

    /**
     * 给队列添加元素
     *
     * @param item 要加入队列的元素
     * @throws Exception 抛出异常
     */
    public void addQueue(int item) throws Exception {
        // 在添加队列元素之前应该先判别队列是否已满
        if (isFull()) {
            throw new Exception("队列已满！");
        } else {
            rear = (rear + 1) % maxSize;
            queue[rear] = item;
        }
    }

    /**
     * 判断队列是否为空
     *
     * @return 如果为空返回true，否则返回false
     */
    public boolean isEmpty() {
        return rear == front;
    }

    /**
     * 删除并返回队列元素
     *
     * @return 返回要删除的队列元素
     * @throws Exception 抛出异常
     */
    public int deleteQueue() throws Exception {
        if (isEmpty()) {
            throw new Exception("队列为空！");
        } else {
            front = (front + 1) % maxSize;
            return queue[front];
        }
    }

    public static void main(String[] args) throws Exception {
        MyQueue queue = new MyQueue(4);
        // 判断队列是否为空
        System.out.println(queue.isEmpty());

        // 要少用一个空间来判别队列是否已满
        // 向队列中添加元素
        queue.addQueue(11);
        queue.addQueue(22);
        queue.addQueue(33);

        // 判断队列是否已满
        System.out.println(queue.isFull());

        // 出队列
        System.out.println(queue.deleteQueue());
        System.out.println(queue.deleteQueue());
        System.out.println(queue.deleteQueue());

        // 判断队列是否为空
        System.out.println(queue.isEmpty());
    }
}

测试，控制台打印：