C++ -- 队列std::queue

C++ 中的队列（Queue）是一种遵循‌先进先出‌（FIFO, First In First Out）原则的线性数据结构。元素从队尾（Rear）进入，从队头（Front）移除。

在 C++ 中，使用队列主要有两种方式：

1. ‌使用 STL 标准库‌：std::queue（最常用、推荐）。
2. ‌手动实现‌：基于数组（循环队列）或链表，用于理解底层原理或特定场景优化。

1. STLstd::queue的使用

std::queue是一个‌容器适配器‌，默认底层使用std::deque（双端队列）实现，也可以指定为std::list。它封装了底层容器的操作，只暴露队列特有的接口。

1.1 基本操作

‌注意‌：pop()函数不返回被删除的元素。如果需要获取并删除队头元素，需先调用front()获取值，再调用pop()。

1.2 代码示例

#include <iostream> #include <queue> #include <string> using namespace std; int main() { // 1. 创建队列 queue<int> q; // 2. 入队 (Push) q.push(10); q.push(20); q.push(30); // 3. 查看状态 cout << "队列大小: " << q.size() << endl; // 输出: 3 cout << "队头元素: " << q.front() << endl; // 输出: 10 cout << "队尾元素: " << q.back() << endl; // 输出: 30 // 4. 出队 (Pop) - 注意 pop 没有返回值 if (!q.empty()) { int val = q.front(); // 先获取值 q.pop(); // 再移除 cout << "出队元素: " << val << endl; // 输出: 10 } // 5. 遍历队列 (队列不支持迭代器，只能通过不断出队来遍历，这会破坏队列) // 如果需要保留原队列，通常复制一份或使用其他容器 while (!q.empty()) { cout << q.front() << " "; q.pop(); } // 输出: 20 30 return 0; }

1.3 自定义底层容器

虽然默认使用deque，但你可以根据需求指定底层容器：

#include <list> #include <queue> // 使用 list 作为底层容器（适合频繁插入删除，但内存开销大） queue<int, list<int>> q_list; // 使用 deque 作为底层容器（默认，缓存友好，支持随机访问但队列接口屏蔽了该功能） queue<int, deque<int>> q_deque;

#include <iostream> #include <stdexcept> using namespace std; template <typename T> class CircularQueue { private: T* data; int front; int rear; int capacity; public: CircularQueue(int size) : capacity(size + 1), front(0), rear(0) { data = new T[capacity]; } ~CircularQueue() { delete[] data; } bool isEmpty() { return front == rear; } bool isFull() { return (rear + 1) % capacity == front; } void push(T val) { if (isFull()) { throw overflow_error("Queue is full"); } data[rear] = val; rear = (rear + 1) % capacity; } void pop() { if (isEmpty()) { throw underflow_error("Queue is empty"); } front = (front + 1) % capacity; } T getFront() { if (isEmpty()) { throw underflow_error("Queue is empty"); } return data[front]; } int size() { return (rear - front + capacity) % capacity; } }; // 测试 int main() { CircularQueue<int> cq(3); // 实际只能存3个元素，因为预留了一个空间 cq.push(1); cq.push(2); cq.push(3); cout << "Front: " << cq.getFront() << endl; // 1 cq.pop(); cout << "Front after pop: " << cq.getFront() << endl; // 2 cq.push(4); // 此时空间复用 cout << "Size: " << cq.size() << endl; // 3 return 0; }