C++线性表：队列详解

队列（Queue）是一种线性数据结构，它具有先进先出（First-In-First-Out，FIFO）的特点，即最先进入队列的元素最先被取出。队列可以通过数组或链表实现。

在 C++ 中，队列可以使用标准库中的 queue 类实现，该类位于头文件 <queue> 中，具有以下常用成员函数：

• push()：将元素加入队列的末尾

• pop()：将队列的首元素删除

• front()：返回队列的首元素

• back()：返回队列的末尾元素

• size()：返回队列中元素的个数

• empty()：判断队列是否为空

下面是使用 queue 类实现队列的示例代码：

#include <iostream>
#include <queue>

using namespace std;

int main() {
    queue<int> q;
    q.push(1);
    q.push(2);
    q.push(3);
    cout << "队列大小：" << q.size() << endl;
    cout << "队列首元素：" << q.front() << endl;
    cout << "队列末尾元素：" << q.back() << endl;
    q.pop();
    cout << "队列大小：" << q.size() << endl;
    cout << "队列首元素：" << q.front() << endl;
    cout << "队列末尾元素：" << q.back() << endl;
    return 0;
}

输出结果为：

队列大小：3
队列首元素：1
队列末尾元素：3
队列大小：2
队列首元素：2
队列末尾元素：3

除了标准库中的 queue 类，我们也可以使用数组或链表实现队列，具体实现可以参考以下示例代码：

使用数组实现队列：

#include <iostream>

using namespace std;

const int MAXSIZE = 100;  // 队列最大长度

class Queue {
public:
    Queue() : head(0), tail(0) {}

    bool enqueue(int x) {
        if (tail == MAXSIZE) {
            return false;  // 队列已满
        }
        q[tail++] = x;
        return true;
    }

    bool dequeue(int& x) {
        if (head == tail) {
            return false;  // 队列已空
        }
        x = q[head++];
        return true;
    }

    bool empty() const {
        return head == tail;
    }

    int size() const {
        return tail - head;
    }

private:
    int q[MAXSIZE];  // 队列数组
    int head;        // 队列头指针
    int tail;        // 队列尾指针
};

int main() {
    Queue q;
    q.enqueue(1);
    q.enqueue(2);
    q.enqueue(3);
    cout << "队列大小：" << q.size() << endl;
    int x;
    q.dequeue(x);
    cout << "出队元素：" << x << endl;
    cout << "队列大小：" << q.size() << endl;
    return 0;
}

使用链表实现队列：

#include <iostream>

using namespace std;

class Node {
public:
    Node(int x) : val(x), next(nullptr) {}

    int val;
    Node* next;
};

class Queue {
public:
    Queue() : head(nullptr), tail(nullptr) {}

    bool enqueue(int x) {
        Node* node = new Node(x);
        if (head == nullptr) {
            head = node;
            tail = node;
        } else {
            tail->next = node;
            tail = node;
        }
        return true;
    }

    bool dequeue(int& x) {
        if (head == nullptr) {
            return false;  // 队列已空
        }
        x = head->val;
        Node* tmp = head;
        head = head->next;
        delete tmp;
        return true;
    }

    bool empty() const {
        return head == nullptr;
    }

    int size() const {
        int cnt = 0;
        Node* p = head;
        while (p != nullptr) {
            cnt++;
            p = p->next;
        }
        return cnt;
    }

private:
    Node* head;  // 队列头指针
    Node* tail;  // 队列尾指针
};

int main() {
    Queue q;
    q.enqueue(1);
    q.enqueue(2);
    q.enqueue(3);
    cout << "队列大小：" << q.size() << endl;
    int x;
    q.dequeue(x);
    cout << "出队元素：" << x << endl;
    cout << "队列大小：" << q.size() << endl;
    return 0;
}

输出结果为：

队列大小：3
出队元素：1
队列大小：2

以上是使用数组或链表手动实现队列的示例代码，需要注意的是，手动实现队列需要自行处理队列空和队列满的情况，而使用标准库中的 queue 类则不需要考虑这些问题，因为 queue 类已经封装好了相关的处理。