03 队列

03-队列

定义

队列（Queue）：具有一定操作约束的线性表

• 插入和删除操作：只能在一端插入，而在另一端删除
• 数据插入：入队列（AddQ）
• 数据删除：出队列（DeleteQ）
• 先进先出：FIFO（First In First Out）

ADT 描述

类型名称：队列（Queue）

数据对象集：一个有 0 个或多个元素的有穷线性表。

操作集：长度为 MaxSize 的队列 \(\text{Q} \in \text{Queue}\)，队列元素 \(\text{item} \in \text{ElementType}\)

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 以及一个记录队列尾元素位置的变量 rear 组成。

包含元素的有效索引区间是 [front, rear - 1] 。

在不断进行入队和出队的过程中，front 和 rear 都在向右移动，当它们到达数组尾部时就无法继续移动了。为了解决此问题，我们可以将数组视为首尾相接的“环形数组”。

对于环形数组，我们需要让 front 或 rear 在越过数组尾部时，直接回到数组头部继续遍历。这种周期性规律可以通过“取余操作”来实现。

#include <iostream>

using ElementType = double;

const int kMaxSize = 100;

class ArrayQueue {
  private:
    ElementType data[kMaxSize];
    int front;
    int rear;

  public:
    bool isFull() const { return (rear + 1) % kMaxSize == front; }

    bool isEmpty() const { return front == rear; }

    /* 入队（队尾） */
    void push(ElementType val) {
        if (isFull()) {
            std::cerr << "Queue is full!\n";
            return;
        }
        data[rear] = val;             // 将元素添加到队尾
        rear = (rear + 1) % kMaxSize; // 循环队列的关键
    }

    /* 出队 */
    ElementType pop() {
        if (isEmpty()) {
            std::cerr << "Queue is empty!\n";
            return NAN;
        }
        ElementType temp = data[front]; // 获取队头元素
        front = (front + 1) % kMaxSize; // 循环队列的关键
        return temp;                    // 返回出队元素
    }

    /* 获取队头元素 */
    ElementType peek() {
        if (isEmpty()) {
            std::cerr << "Queue is empty!\n";
            return NAN;
        }
        return data[front];
    }
};

注意，在数组的结构上，入队看起来似乎是在往数组右（下）边添加元素，像是在队首添加元素一样，实际上是在队尾添加元素，改变的是 rear 的值。

问题又来了，环形数组在 rear == front 的时候既可能是空的也可能是满的。本质是因为默认情况下，装载情况一共有 \(n+1\) 种，对应 \(0,1,\ldots,n\)，而 rear 和 front 的相对位置对应的情况只有 \(n\) 种，因此必然有一种 rear 和 front 的组合对应两种装载情况，即空和满。

链式实现

使用一个单链表实现。插入在链表的头进行，删除在链表的尾进行，因为头可以进行插入和删除，但是尾只能插入，删除时找不到前一结点的位置。

#include <iostream>

using ElementType = double;

class LinkedListQueue {
  private:
    struct Node {
        ElementType data;
        Node* next;
        Node() : next(nullptr) {}
        Node(ElementType val) : data(val), next(nullptr) {}
    };

    Node* front;
    Node* rear;

  public:
    LinkedListQueue() : front(nullptr), rear(nullptr) {}

    bool isEmpty() const { return front == nullptr; }

    /* 入队 */
    void push(ElementType val) {
        Node* newNode = new Node{val};
        if (isEmpty()) {
            front = rear = newNode;
        } else {
            rear->next = newNode;
            rear = newNode;
        }
    }

    /* 出队 */
    ElementType pop() {
        if (isEmpty()) {
            std::cerr << "Queue is empty!\n";
            return NAN;
        }
        ElementType temp = front->data;
        Node* del = front;
        if (front == rear) { /* 只剩一个节点，删除后需要更新front和rear指针 */
            front = rear = nullptr;
        } else { /* 多于一个节点，只更新front指针 */
            front = front->next;
        }
        delete del;
        return temp;
    }

    /* 获取队首元素 */
    ElementType peek() {
        if (isEmpty()) {
            std::cerr << "Queue is empty!\n";
            return NAN;
        }
        return front->data;
    }
};

应用：多项式加法运算