【数据结构】队列的完整实现

下面是一个从零开始的队列（Queue）数据结构完整实现讲解，涵盖 顺序队列（数组实现）、链式队列（链表实现） 和 循环队列 三种方式，适用于学习数据结构、面试准备或算法练习。

📘 目录

1. 顺序队列（数组实现）
2. 链式队列（链表实现）
3. 循环队列（解决“假溢出”问题）
4. 适配 STL 的 C++ 队列简要介绍
5. 常见操作总结

1. ✅ 顺序队列（数组实现）

📌 特点

• 使用数组固定容量存储；
• front 指向队首元素，rear 指向队尾后一位；
• 插入时从 rear 进，删除从 front 出；
• 容易出现“假溢出”。

🧠 代码实现（C++）

#include <iostream>
using namespace std;

const int MAX_SIZE = 100;

class Queue {
private:
    int data[MAX_SIZE];
    int front, rear;
public:
    Queue() {
        front = rear = 0;
    }

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

    bool isFull() {
        return rear == MAX_SIZE;
    }

    bool enqueue(int val) {
        if (isFull()) return false;
        data[rear++] = val;
        return true;
    }

    bool dequeue(int &val) {
        if (isEmpty()) return false;
        val = data[front++];
        return true;
    }

    int getFront() {
        if (isEmpty()) throw "Queue is empty";
        return data[front];
    }

    int size() {
        return rear - front;
    }
};

2. ✅ 链式队列（链表实现）

📌 特点

• 不存在容量限制；
• 动态申请空间，不会出现假溢出；
• 操作效率高，适合大数据量。

🧠 代码实现（C++）

#include <iostream>
using namespace std;

struct Node {
    int val;
    Node* next;
    Node(int x) : val(x), next(nullptr) {}
};

class LinkedQueue {
private:
    Node *front, *rear;
public:
    LinkedQueue() {
        front = rear = nullptr;
    }

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

    void enqueue(int val) {
        Node* node = new Node(val);
        if (rear) rear->next = node;
        rear = node;
        if (!front) front = node;
    }

    bool dequeue(int &val) {
        if (isEmpty()) return false;
        Node* tmp = front;
        val = front->val;
        front = front->next;
        if (!front) rear = nullptr;
        delete tmp;
        return true;
    }

    int getFront() {
        if (isEmpty()) throw "Queue is empty";
        return front->val;
    }
};

3. ✅ 循环队列（Circular Queue）

📌 特点

• 利用取模操作实现“环形”数组；
• 不再出现“假溢出”；
• 判空条件：front == rear；
• 判满条件：(rear + 1) % MAX_SIZE == front

🧠 代码实现（C++）

#include <iostream>
using namespace std;

const int MAX_SIZE = 100;

class CircularQueue {
private:
    int data[MAX_SIZE];
    int front, rear;
public:
    CircularQueue() {
        front = rear = 0;
    }

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

    bool isFull() {
        return (rear + 1) % MAX_SIZE == front;
    }

    bool enqueue(int val) {
        if (isFull()) return false;
        data[rear] = val;
        rear = (rear + 1) % MAX_SIZE;
        return true;
    }

    bool dequeue(int &val) {
        if (isEmpty()) return false;
        val = data[front];
        front = (front + 1) % MAX_SIZE;
        return true;
    }

    int getFront() {
        if (isEmpty()) throw "Queue is empty";
        return data[front];
    }

    int size() {
        return (rear - front + MAX_SIZE) % MAX_SIZE;
    }
};

4. 🛠 STL 队列（std::queue 简介）

在 C++ 中，标准库已提供 std::queue 和 std::deque 容器：

#include <queue>
#include <iostream>
using namespace std;

int main() {
    queue<int> q;
    q.push(10); q.push(20);
    cout << q.front() << endl; // 输出 10
    q.pop();
    cout << q.front() << endl; // 输出 20
}

5. ✅ 队列常用操作总结