Java顺序队列（队列的顺序存储）用法详解

顺序队列通常采用数组作为存储结构。同时，用两个指针分别指向数组中的第一个元素和最后一个元素：

• 指向第一个元素的指针称为队头指针（front）；
• 指向最后一个元素的位置的指针称为队尾指针（rear）。

顺序队列的表示如下图所示：


为了方便描述，我们约定：初始化时，队列为空，有 front=rear=0，队头指针 front 和队尾指针 rear 都指向队列的第一个位置，如下图所示：


插入新元素时，队尾指针 rear 增加 1，在空队列中插入 4 个元素 a、b、c、d 之后，如下图所示：


删除元素时，队头指针 front 增加 1。删除 2 个元素 a、b 之后，队头指针和队尾指针的状态如下图所示：


顺序队列的类型描述如下：

public class SeQueue<T> {
    final int QUEUESIZE = 20;
    T s[];
    int front, rear;
    SeQueue() {
        //顺序循环队列的初始化
        s = (T[]) new Object[QUEUESIZE];
        front = 0;  //把队头指针置为 0
        rear = 0;   //把队尾指针置为 0
    }
}

假设 Q 是一个队列，若不考虑队满，则入队操作语句为Q.s[rear]=x、rear++；若不考虑队空，则出队操作语句为x=Q.s[front]、front++。

在队列中，队满指的是元素占据了队列中的所有存储空间，没有空闲的存储空间可以插入元素。队空指的是队列中没有一个元素，也称为空队列。

顺序队列的“假溢出”

如果在如下图所示的队列中插入 3 个元素 j、k 和 l，然后删除 2 个元素 a、b：


就会出现如图 6 所示的情况：


即队尾指针已经到达数组的末尾，如果继续插入元素 m，队尾指针将越出数组的下界而造成“溢出”。

从图 6 可以看出，这种“溢出”不是因为存储空间不够，而是经过多次插入和删除操作产生的，我们将这种“溢出”称为“假溢出”。

为了避免顺序队列的“假溢出”，通常采用顺序循环队列来实现队列的顺序存储。

顺序循环队列

1) 顺序循环队列的构造

为了充分利用存储空间，消除这种“假溢出”，当队尾指针 rear（或队头指针 front）到达存储空间的最大值 QUEUESIZE 的时候，让队尾指针 rear（或队头指针 front）自动转化为存储空间的最小值 0。

这样，顺序队列的存储空间就构成一个逻辑上首尾相连的循环队列：

• 当队尾指针 rear 达到最大值 QUEUESIZE -1 时，若要插入新的元素，则队尾指针 rear 自动变为 0；
• 当队头指针 front 达到最大值 QUEUESIZE -1 时，若要删除一个元素，则队头指针 front 自动变为 0。

可通过取余操作实现循环队列的首尾相连。例如，若 QUEUESIZE=10，当队尾指针 rear=9 时，若要插入一个新的元素，则有 rear=(rear+1)%10=0，即实现了逻辑上队列的首尾相连。

2) 顺序循环队列的队空和队满

顺序循环队列在队空状态和队满状态时，队头指针 front 和队尾指针 rear 同时指向一个位置，即 front==rear，顺序循环队列的队空状态和队满状态如下图所示。


队空状态时，有 front=0、rear=0，因此 front==rear。队满状态时，也有 front=0、rear=0，因此 front==rear。

因此，为了区分这两种情况，通常有如下两种方法：

1) 增加一个标志位。设这个标志位为 flag，初始化为 flag=false，当入队成功时，有 flag=true；当出队成功时，有 flag=false：

• 队空的判断条件为：front==rear&&flag==false；
• 队满的判断条件为：front==rear&&flag==true。

2) 少用一个存储空间。队空的判断条件不变，以队尾指针 rear 加 1 等于 front 为队满的判断条件。因此，front==rear 表示队空，front==(rear+1)% QUEUESIZE 表示队满。那么：

• 入队的操作语句为 rear=(rear+1)% QUEUESIZE，Q[rear]=x；
• 出队的操作语句为 front=(front+1)% QUEUESIZE。

少用一个存储空间时，队满情况如下图所示。


注意：顺序循环队列中的入队操作和出队操作都要取模，以确保操作不出界。循环队列长度，即元素个数为 (SQ.rear+ QUEUESIZE-SQ.front)% QUEUESIZE。

顺序循环队列的实现

1) 初始化

SeQueue() {
    // 顺序循环队列的初始化
    s = (T[]) new Object[QUEUESIZE];
    front = 0;    // 把队头指针置为 0
    rear = 0;     // 把队尾指针置为 0
}

2) 判断队列是否为空

public boolean IsEmpty() // 判断顺序循环队列是否为空
{
    if (front == rear) // 当顺序循环队列为空时
        return true;   // 返回 true
    else             // 否则
        return false;  // 返回 false
}

3) 入队操作

public boolean EnQueue(T x)
//元素 e 插入顺序循环队列中，若插入成功，则返回 true，否则返回 false
{
    if ((rear + 1) % QUEUESIZE != front)  //若队列未满
    {
        s[rear] = x;                    //在队尾插入元素 e
        rear = (rear + 1) % QUEUESIZE;  //将队尾指针向后移动一个位置
        return true;
    } else {
        System.out.println("当前队列已满!");
        return false;
    }
}

4) 出队操作

public T DeQueue() throws Exception {
    //将队头元素出队，并将该元素赋值给 e，若删除成功，则返回出队元素
    if (front == rear)  //若队列为空
    {
        throw new Exception("队列为空，不能进行出队操作");
    }
    else
    {
        T e = s[front];  //将待出队的元素赋值给 e
        front = (front + 1) % QUEUESIZE;  //将队头指针向后移动一个位置，指向新的队头
        return e;  //返回出队的元素
    }
}

5) 取队头元素

public T GetHead() throws Exception {
    //取队头元素，并将该元素返回，若队列为空，则返回 False
    if (!IsEmpty())  //若顺序循环队列不为空
        return (T)s[front];  //返回队头元素
    else {
        throw new Exception("队列为空");
    }
}

6) 求队列的长度

public int SeqLength() {
    return (rear - front + QUEUESIZE) % QUEUESIZE;
}

7) 创建队列

public void CreateSeqQueue()
{
    System.out.println("请输入元素（#作为输入结束）：");
    Scanner sc = new Scanner(System.in);
    Integer data = sc.nextInt();
    while (data != -1) {
        EnQueue(data);
        data = sc.nextInt();
    }
}