数据结构笔记03：队列

1.队列的抽象类

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() {}
};

2.顺序存储实现

实现分类

使用数组存储队列中的元素。
节点个数用MaxSize维护。
下标范围为0到MaxSize-1。
分三种组织方式：
- 队头位置固定：出队会引起大量的数据移动。
- 队头位置不固定：操作为O(1)，但需要记录队头和队尾的位置,同时会浪费数组空间。
- 循环队列：队头和队尾位置可以循环使用，避免了空间浪费，同时避免大量的数据移动。

3.循环队列

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

操作实现

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

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。即队头追上了队尾。

类定义

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 seqQuene<elemType>::doubleSpace()
{
    elemType* tmp = elem;
    elem = new elemType[2 * maxSize];
    for (int i = 0; i < maxSize; ++i) {
        elem[i] = tmp[(front + i) % maxSize]; // 重新排列元素
    }
    front = 0; // 重置队头位置
    rear = 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; // 队头追上队尾，表示队列为空
}