C++如何实现一个队列(Queue)_C++数据结构之先进先出(FIFO)的实现

答案：C++中队列可通过链表、循环数组或STL实现，链表法便于理解FIFO原理，循环队列节省空间，STL的queue最实用。

在C++中实现一个队列（Queue），核心是遵循先进先出（FIFO, First In First Out）的原则。可以通过数组、链表或使用STL容器来实现。下面从零开始，介绍如何手动实现一个基于链表的队列，并简要说明其他实现方式。

1. 链表实现队列（推荐初学者理解原理）

使用单向链表可以高效地实现队列，其中队头用于出队（dequeue），队尾用于入队（enqueue），避免频繁移动数据。

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

class Queue { private: Node front; // 指向队头 Node rear; // 指向队尾

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

// 入队：在队尾添加元素
void enqueue(int val) {
    Node* newNode = new Node(val);
    if (rear == nullptr) {
        front = rear = newNode;
    } else {
        rear->next = newNode;
        rear = newNode;
    }
}

// 出队：从队头移除元素
void dequeue() {
    if (front == nullptr) {
        std::cout << "队列为空，无法出队\n";
        return;
    }
    Node* temp = front;
    front = front->next;
    if (front == nullptr) {
        rear = nullptr;  // 队列变空时更新rear
    }
    delete temp;
}

// 获取队头元素
int getFront() {
    if (front == nullptr) {
        throw std::runtime_error("队列为空");
    }
    return front->data;
}

// 判断队列是否为空
bool isEmpty() {
    return front == nullptr;
}

// 析构函数：释放内存
~Queue() {
    while (front != nullptr) {
        Node* temp = front;
        front = front->next;
        delete temp;
    }
}

};

2. 使用动态数组实现循环队列（节省空间）

如果用数组实现，为了避免大量数据前移，可采用“循环队列”结构，通过取模操作复用空间。

class CircularQueue { private: int* arr; int front, rear; int capacity; int count;

public: CircularQueue(int size) { capacity = size; arr = new int[capacity]; front = 0; rear = -1; count = 0; }

void enqueue(int val) {
    if (count == capacity) {
        std::cout << "队列已满\n";
        return;
    }
    rear = (rear + 1) % capacity;
    arr[rear] = val;
    count++;
}

void dequeue() {
    if (count == 0) {
        std::cout << "队列为空\n";
        return;
    }
    front = (front + 1) % capacity;
    count--;
}

int getFront() {
    if (count == 0) throw std::runtime_error("队列为空");
    return arr[front];
}

bool isEmpty() {
    return count == 0;
}

~CircularQueue() {
    delete[] arr;
}

};