数据结构-03：队列

队列的抽象类

template <class elemType>
class queue
{
public:
    virtual bool isEmpty() const = 0;
    virtual void enQueue(const elemType &x) = 0;
    virtual elemType deQueue() = 0;
    virtual elemType getHead() const = 0;
    virtual ~queue() {}
};

队列的规则是先进先出：只能从队尾入队，从队头出队。可以把它想成排队买票，先进入队伍的人先被服务。后续顺序队列和链式队列的实现差异，主要在于如何高效维护“队头”和“队尾”这两个位置。

顺序存储实现

队列的顺序存储实现看似可以直接用数组，但如果每次出队都把后面的元素整体前移，代价会退化为 $O(n)$ 。因此更合理的做法是让队头位置也移动起来，只维护队头、队尾两个下标。循环队列进一步把数组尾部和头部逻辑上接起来，让已经出队释放出的空间可以重新使用。

顺序队列的难点不在入队或出队本身，而在数组空间被反复使用后，逻辑顺序和物理下标不再一致。后面的循环队列正是为了解决这个问题。

实现分类

使用数组存储队列中的元素。
节点个数用 MaxSize 维护。
下标范围为 0 到 MaxSize-1。
分三种组织方式：

队头位置固定：出队会引起大量的数据移动。
队头位置不固定：操作为 $O(1)$ ，但需要记录队头和队尾的位置，同时会浪费数组空间。
循环队列：队头和队尾位置可以循环使用，避免了空间浪费，同时避免大量的数据移动。

循环队列

front 指向队头前方的位置。
rear 指向队尾位置。

循环队列的核心是把数组下标看成一个环。普通数组走到末尾就不能继续使用前面释放出来的位置，而循环队列用 % maxSize 让下标回绕，从而复用已经出队的空间。front 不直接指向队头元素，而是指向队头前一格；这样空队列可以统一表示为 front == rear。

操作实现

循环队列的操作要围绕两个判断展开：什么时候为空，什么时候为满。由于 front == rear 既可能表示空，也可能表示满，所以常见做法是牺牲一个数组单元，或者额外维护元素个数。本笔记采用牺牲一个单元的方法，使得空队列和满队列能用两个不同条件区分。

只要记住 front 是队头前一格、rear 是队尾元素位置，入队就是先移动 rear 再写入，出队就是先移动 front 再读出。

改进前：队头可以存储元素

1 2	rear = (rear + 1) % maxSize; elem[rear] = x;// 入队 front = (front + 1) % maxSize; // 出队

最后一个元素出队时，front = (front + 1) % maxSize，front 和 rear 相等，表示队列为空。
只剩最后一个空位置，执行入队操作，rear = (rear + 1) % maxSize，front 和 rear 相等，表示队列满。

循环队列 front 除了初始状态时，其余时间不一定指向 0 号下标。Front 和 rear“你逃我追”

改进后：队头不存储元素

“牺牲”一个单元，规定 front 指向的单元不能存储队列元素，只起到标志作用，表示后面一个是队头元素。
当 rear “绕一卷”赶上 front 时，队列就满了。因此队列满的条件是 (rear + 1) % maxSize == front。
队列空的条件是 rear == front，即队头追上了队尾。

这里故意空出一个单元，是为了区分“空”和“满”。如果不牺牲这个单元，front == rear 既可能表示没有元素，也可能表示数组刚好被填满，代码就必须额外维护元素个数。牺牲一个单元后，判断条件更简单：rear == front 是空，rear 的下一格是 front 则是满。

类定义

template <class elemType>
class seqQueue: public queue<elemType>
{
private:
    elemType *elem; // 循环数组
    int front;      // 队头前一格，作为哨兵单元
    int rear;       // 队尾元素所在位置
    int maxSize;    // 数组容量，其中一个单元不存储元素
    void doubleSpace(); // 队满时扩容并重排元素
public:
    seqQueue(int initSize = 10);
    ~seqQueue();
    bool isEmpty() const;
    void enQueue(const elemType &x);
    elemType deQueue();
    elemType getHead() const;
};

类实现

//构造函数
template <class elemType>
seqQueue<elemType>::seqQueue(int initSize)
{
    elem = new elemType[initSize];
    maxSize = initSize;
    front = 0;
    rear = 0;
}

//析构函数
template <class elemType>
seqQueue<elemType>::~seqQueue()
{
    delete[] elem;
}

//入队
template <class elemType>
void seqQueue<elemType>::enQueue(const elemType &x)
{
    if ((rear + 1) % maxSize == front) doubleSpace(); // 队列满时扩容
    rear = (rear + 1) % maxSize; // 更新队尾位置
    elem[rear] = x; // 新元素写入新的队尾
}

//扩充空间
template <class elemType>
void seqQueue<elemType>::doubleSpace()
{
    elemType* tmp = elem;
    elem = new elemType[2 * maxSize];
    for (int i = 1; i < maxSize; ++i) {
        elem[i] = tmp[(front + i) % maxSize]; // 从front后一格开始搬移真实元素
    }
    front = 0; // 重置队头位置
    rear = maxSize - 1; // 原来最多存放maxSize-1个元素
    maxSize *= 2; // 更新最大容量
    delete [] tmp; // 释放旧空间
}

//出队
template <class elemType>
elemType seqQueue<elemType>::deQueue()
{
    if (isEmpty()) throw "Queue is empty"; // 队列为空时抛出异常
    front = (front + 1) % maxSize; // 更新队头位置
    return elem[front]; // 返回队头元素
}

//判队空
template <class elemType>
bool seqQueue<elemType>::isEmpty() const
{
    return front == rear; // 队头追上队尾，表示队列为空
}

//读队头
template <class elemType>
elemType seqQueue<elemType>::getHead() const
{
    if (isEmpty()) throw "Queue is empty";
    return elem[(front + 1) % maxSize]; // front后一格才是真正的队头元素
}

这段实现最值得关注的是 doubleSpace()。扩容时不能简单地从旧数组下标 0 开始复制，因为队列元素可能已经在环上“断开”成两段。代码从 front 的后一格开始，按队列逻辑顺序搬移 maxSize - 1 个可能存在的元素，把它们重新整理到新数组的 1..maxSize-1 区间。整理完成后，front 被重置为 0，rear 指向最后一个旧元素的位置，队列又恢复成连续形态。