lec3 List Stack Queue（3)

关于链表，栈，队列。

列表抽象数据类型（Queue ADT）导读

队列的重点在于各种队列的类型以及需要注意什么问题，其他一带而过即可。

队列：定义与关键概念

队列（Queue） 是一种线性数据结构，遵循 先进先出（FIFO, First-In, First-Out） 的原则。即：最先进入队列的元素会最先被移除，类似排队等待服务的场景。

关键操作

入队（Enqueue）：将元素插入到队列的尾部。
出队（Dequeue）：从队列的头部移除元素。
访问队首（FrontValue）：获取队列中位于头部的元素，但不移除。
清空队列（Clear）：移除队列中所有元素。
获取长度（Length）：返回队列中元素的数量。

队列抽象类模板

下面的 Queue 模板定义了队列的抽象基类，用于实现具体的队列类型（如基于数组的队列或基于链表的队列）。

模板定义

template <typename E>
class Queue {
private:
    void operator=(const Queue&) {} // 禁止赋值
    Queue(const Queue&) {};         // 禁止拷贝构造
public:
    Queue() {}                      // 构造函数
    virtual ~Queue() {}             // 析构函数

    // 纯虚函数（需在派生类中实现）
    virtual void clear() = 0;                     // 清空队列
    virtual void enqueue(const E&) = 0;           // 插入元素到队尾
    virtual E dequeue() = 0;                      // 移除队首元素
    virtual const E& frontValue() const = 0;      // 访问队首元素
    virtual int length() const = 0;               // 获取队列长度
};

队列的类型

基于数组的队列。（重点，尤其是各种队列）

基于指针的队列。

固定索引的队列问题

选择数组位置 0 作为队列头部
- 入队：
  - 元素插入到 rear 指向的位置，时间复杂度为 $O(1)$。
- 出队：
  - 移除 front 元素后，需要将数组剩余元素前移，时间复杂度为 $O(n)$。
- 缺点：出队性能较差。
选择数组位置 $n-1$ 作为队列头部
- 入队：
  - 新元素插入到队列前端，时间复杂度为 $O(n)$。
- 出队：
  - 直接移除 front 元素，时间复杂度为 $O(1)$。
- 缺点：入队性能较差。

优化方法：漂移队列（Drifting Queue）

漂移队列通过让索引 front 和 rear 随操作漂移，而不移动数组中的数据，优化了时间复杂度。

实现细节

初始化
- front 指向数组的开头位置（0）。
- rear 初始为 -1，表示队列为空。
入队（enqueue）
- 将元素添加到 rear + 1 指向的位置。
- 更新 rear，使其指向新插入的元素。
- 时间复杂度：$O(1)$。
出队（dequeue）
- 移除 front 索引处的元素。
- 更新 front，使其指向下一个元素。
- 时间复杂度：$O(1)$。
漂移
- 随着出队操作，front 索引逐渐向右移动。
- 当 rear 索引到达数组末尾，数组可能需要重置或扩展。

漂移队列的优缺点

优点

操作高效：
- 入队和出队的时间复杂度均为 $O(1)$。
实现简单：
- 不需要复杂的取模操作。

缺点：

空间浪费：
- 随着 front 和 rear 索引漂移，数组前部可能留有大量未使用空间。
- 解决办法是当 front 索引漂移到一定程度时，可以进行数组压缩或扩展。

Problem

漂移队列的扩展：循环队列

引入

漂移队列是循环队列的基础。如果使用取模操作（modulus），可以避免数组空间浪费，进一步提升性能。

循环队列特点：

队首和队尾索引使用 (index + 1) % maxSize 更新。
空间利用率高，无需担心数组漂移问题。

什么是循环队列？

循环队列是一种队列的实现方式，使用数组存储元素，当到达数组末尾时会回到开头继续存储。通过使用取模（modulus）操作处理索引，循环队列可以避免线性队列中因元素出队而导致的空间浪费问题。

关键特性

循环性质：
- 数组的最后一个位置逻辑上与第一个位置相连，形成一个闭环结构。
空间高效：
- 出队操作后腾出的空间可以被重新利用，而不像线性队列那样浪费。
基本操作：
- 入队 (enqueue)：在队尾添加一个元素。
- 出队 (dequeue)：从队首移除一个元素。
空队列和满队列的区分：
- 循环队列需要额外的判断逻辑来区分队列为空或已满，因为两种情况都可能导致 front == rear+1。

空队列和满队列的区分

方法 1：增加一个变量 count，记录当前队列中的元素个数。
方法 2：数组长度设置为 $ n+1 $，最多允许存储 $ n $ 个元素。这样可以利用空余一个位置区分队列为空或已满。
- 当 front == rear + 1 时，队列为空。
- 当 front == rear + 2 时，队列已满。

第二种方法可能会在考试中出现。

循环队列的数组实现代码

类定义

template <typename E>
class AQueue : public Queue<E> {
private:
    int maxSize;       // 队列的最大容量（数组大小为 maxSize+1）
    int front;         // 队首索引
    int rear;          // 队尾索引
    E* listArray;      // 存储队列元素的数组

public:
    // 构造函数
    AQueue(int size = defaultSize) {
        maxSize = size + 1;  // 数组大小多预留一个位置
        rear = 0;
        front = 1;
        listArray = new E[maxSize];
    }

    // 析构函数
    ~AQueue() {
        delete[] listArray;
    }

    // 清空队列
    void clear() {
        rear = 0;
        front = 1;
    }

    // 入队操作
    void enqueue(const E& it) {
        Assert(((rear + 2) % maxSize) != front, "队列已满");
        rear = (rear + 1) % maxSize;  // 更新队尾索引
        listArray[rear] = it;         // 插入元素
    }

    // 出队操作
    E dequeue() {
        Assert(length() != 0, "队列为空");
        E it = listArray[front];      // 保存队首元素
        front = (front + 1) % maxSize; // 更新队首索引
        return it;
    }

    // 获取队首元素
    const E& frontValue() const {
        Assert(length() != 0, "队列为空");
        return listArray[front];
    }

    // 获取队列长度
    virtual int length() const {
        return ((rear + maxSize) - front + 1) % maxSize;
    }
};

时间复杂度分析

操作	时间复杂度
入队操作	$ O(1) $
出队操作	$ O(1) $
获取队首元素	$ O(1) $
清空队列	$ O(1) $

基于链表的队列（Linked Queue）

什么是链式队列？

链式队列是一种使用链表结构实现的队列。它由动态分配的节点组成，通过链表中的指针链接各个节点。与数组队列不同，链式队列没有固定的容量限制，能高效处理动态变化的队列操作。

链式队列的结构

头节点 (Header Node)：
- 使用一个头节点（不存储队列元素）作为队列的起点。
- 队列的 front 指针始终指向头节点。
尾节点：
- 队列的 rear 指针指向链表的最后一个节点。
- 用于快速插入新元素。
节点定义：
- 每个节点包含两部分：
  - 数据域 (data)：存储队列元素。
  - 指针域 (next)：指向下一个节点。

基本操作

入队操作 (Enqueue)：
- 将新元素放入链表末尾，并更新 rear 指针。
- 时间复杂度：$ O(1) $。
出队操作 (Dequeue)：
- 移除队列的第一个元素，并更新 front 指针。
- 时间复杂度：$ O(1) $。
其他操作：
- 获取队首元素。
- 判断队列是否为空。
- 清空队列。

链式队列的实现代码

节点定义

template <typename E>
struct Node {
    E data;        // 数据域
    Node* next;    // 指针域，指向下一个节点

    // 构造函数
    Node(const E& d, Node* n = nullptr) : data(d), next(n) {}
};

链式队列类定义

template <typename E>
class LQueue : public Queue<E> {
private:
    Node<E>* front;   // 指向头节点
    Node<E>* rear;    // 指向尾节点
    int size;         // 队列中的元素数量

public:
    // 构造函数
    LQueue() {
        front = rear = new Node<E>(E()); // 初始化头节点
        size = 0;
    }

    // 析构函数
    ~LQueue() {
        clear();
        delete front;
    }

    // 清空队列
    void clear() {
        while (front->next != nullptr) {
            Node<E>* temp = front->next;
            front->next = temp->next;
            delete temp;
        }
        rear = front;
        size = 0;
    }

    // 入队操作
    void enqueue(const E& it) {
        rear->next = new Node<E>(it);  // 创建新节点并链接到尾节点
        rear = rear->next;            // 更新尾节点
        size++;
    }

    // 出队操作
    E dequeue() {
        Assert(size != 0, "队列为空");
        Node<E>* temp = front->next;  // 记录第一个有效节点
        E it = temp->data;           // 获取队首元素
        front->next = temp->next;    // 移除节点
        if (rear == temp) {          // 若队列只有一个节点
            rear = front;            // 更新尾指针
        }
        delete temp;
        size--;
        return it;
    }

    // 获取队首元素
    const E& frontValue() const {
        Assert(size != 0, "队列为空");
        return front->next->data;
    }

    // 返回队列长度
    int length() const {
        return size;
    }
};