C++实现队列结构_FIFO先进先出详解

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

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

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

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

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. 使用动态数组实现循环队列（节省空间）

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

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;
}

};

3. 使用STL中的queue（实际开发推荐）

在实际编程中，建议直接使用C++标准库提供的queue，它封装了底层细节，安全高效。

q.push(10); // 入队 q.push(20); if (!q.empty()) { std::cout << q.front() << "\n"; // 查看队头 q.pop(); // 出队 }

说明： STL的queue默认基于deque实现，也可指定list或vector作为底层容器。

4. 关键点总结

实现队列时需要注意以下几点：

• 保持front和rear指针（或下标）正确更新
• 处理空队列和满队列的边界情况
• 链表实现注意内存释放，防止泄漏
• 循环队列中使用取模实现“环形”逻辑
• 所有基本操作应尽量保持O(1)时间复杂度

基本上就这些。手动实现有助于理解FIFO机制，而项目中优先使用STL更稳妥。