队列
队列是遵循先进先出 (FIFO) 原则的线性数据结构。元素从后端添加（入队）并从前端移除（出队）。可以想象成排队等候的人群 - 第一个排队的人首先得到服务。
队列在计算机科学中对于任务调度、广度优先搜索、处理 Web 服务器中的请求以及许多其他需要公平性和顺序的应用程序是必不可少的。
队列操作
队列的主要操作有：
- enqueue(): 向队尾添加元素
- dequeue(): 从队首移除元素
- front(): 查看队首元素但不移除
- empty(): 检查队列是否为空
- size(): 获取元素数量
使用数组实现队列
#include <iostream>
using namespace std;
class Queue {
private:
int* arr;
int capacity;
int frontIndex;
int rearIndex;
int count;
public:
Queue(int size) {
arr = new int[size];
capacity = size;
frontIndex = 0;
rearIndex = -1;
count = 0;
}
~Queue() {
delete[] arr;
}
// Add element to rear
void enqueue(int value) {
if (count >= capacity) {
cout << "Queue Overflow! Cannot enqueue " << value << endl;
return;
}
rearIndex = (rearIndex + 1) % capacity;
arr[rearIndex] = value;
count++;
cout << "Enqueued: " << value << endl;
}
// Remove element from front
int dequeue() {
if (count <= 0) {
cout << "Queue Underflow! Cannot dequeue from empty queue" << endl;
return -1;
}
int value = arr[frontIndex];
frontIndex = (frontIndex + 1) % capacity;
count--;
return value;
}
// Get front element
int front() {
if (count <= 0) {
cout << "Queue is empty" << endl;
return -1;
}
return arr[frontIndex];
}
// Check if queue is empty
bool empty() {
return count == 0;
}
// Get size of queue
int size() {
return count;
}
// Display queue contents
void display() {
if (empty()) {
cout << "Queue is empty" << endl;
return;
}
cout << "Queue contents (front to rear): ";
for (int i = 0; i < count; i++) {
int index = (frontIndex + i) % capacity;
cout << arr[index] << " ";
}
cout << endl;
}
};
int main() {
Queue queue(5);
// Enqueue elements
queue.enqueue(10);
queue.enqueue(20);
queue.enqueue(30);
queue.display();
cout << "Front element: " << queue.front() << endl;
cout << "Queue size: " << queue.size() << endl;
// Dequeue elements
cout << "Dequeued: " << queue.dequeue() << endl;
cout << "Dequeued: " << queue.dequeue() << endl;
queue.display();
// Add more elements
queue.enqueue(40);
queue.enqueue(50);
queue.display();
return 0;
}STL 队列
C++ 标准模板库提供了一个队列容器适配器：
使用 STL 队列
#include <iostream>
#include <queue>
using namespace std;
int main() {
queue<int> q;
// Enqueue elements
q.push(10);
q.push(20);
q.push(30);
q.push(40);
cout << "Queue size: " << q.size() << endl;
cout << "Front element: " << q.front() << endl;
cout << "Back element: " << q.back() << endl;
// Display and dequeue all elements
cout << "Queue contents: ";
while (!q.empty()) {
cout << q.front() << " ";
q.pop();
}
cout << endl;
// Queue of strings
queue<string> stringQueue;
stringQueue.push("First");
stringQueue.push("Second");
stringQueue.push("Third");
cout << "String queue: ";
while (!stringQueue.empty()) {
cout << stringQueue.front() << " ";
stringQueue.pop();
}
cout << endl;
return 0;
}优先队列
优先队列是一种特殊类型的队列，其中元素根据其优先级而不是到达顺序来服务：
STL 优先队列
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
int main() {
// Max heap (default) - largest element has highest priority
priority_queue<int> maxHeap;
maxHeap.push(30);
maxHeap.push(10);
maxHeap.push(50);
maxHeap.push(20);
cout << "Priority Queue (Max Heap): ";
while (!maxHeap.empty()) {
cout << maxHeap.top() << " ";
maxHeap.pop();
}
cout << endl;
// Min heap - smallest element has highest priority
priority_queue<int, vector<int>, greater<int>> minHeap;
minHeap.push(30);
minHeap.push(10);
minHeap.push(50);
minHeap.push(20);
cout << "Priority Queue (Min Heap): ";
while (!minHeap.empty()) {
cout << minHeap.top() << " ";
minHeap.pop();
}
cout << endl;
// Priority queue with custom priority
struct Task {
string name;
int priority;
Task(string n, int p) : name(n), priority(p) {}
bool operator<(const Task& other) const {
return priority < other.priority; // Higher priority value = higher priority
}
};
priority_queue<Task> taskQueue;
taskQueue.push(Task("Low Priority Task", 1));
taskQueue.push(Task("High Priority Task", 5));
taskQueue.push(Task("Medium Priority Task", 3));
cout << "Task Priority Queue:" << endl;
while (!taskQueue.empty()) {
Task task = taskQueue.top();
cout << task.name << " (Priority: " << task.priority << ")" << endl;
taskQueue.pop();
}
return 0;
}循环队列
循环队列通过将数组视为环形（将末端连接回开头）来有效利用内存：
循环队列实现
#include <iostream>
using namespace std;
class CircularQueue {
private:
int* arr;
int capacity;
int front;
int rear;
int count;
public:
CircularQueue(int size) {
arr = new int[size];
capacity = size;
front = 0;
rear = -1;
count = 0;
}
~CircularQueue() {
delete[] arr;
}
bool enqueue(int value) {
if (isFull()) {
cout << "Queue is full! Cannot enqueue " << value << endl;
return false;
}
rear = (rear + 1) % capacity;
arr[rear] = value;
count++;
return true;
}
int dequeue() {
if (isEmpty()) {
cout << "Queue is empty! Cannot dequeue" << endl;
return -1;
}
int value = arr[front];
front = (front + 1) % capacity;
count--;
return value;
}
int getFront() {
if (isEmpty()) {
cout << "Queue is empty!" << endl;
return -1;
}
return arr[front];
}
bool isEmpty() {
return count == 0;
}
bool isFull() {
return count == capacity;
}
int size() {
return count;
}
void display() {
if (isEmpty()) {
cout << "Queue is empty" << endl;
return;
}
cout << "Queue: ";
for (int i = 0; i < count; i++) {
int index = (front + i) % capacity;
cout << arr[index] << " ";
}
cout << endl;
}
};
int main() {
CircularQueue cq(5);
// Fill the queue
for (int i = 1; i <= 5; i++) {
cq.enqueue(i * 10);
}
cq.display();
// Try to add one more (should fail)
cq.enqueue(60);
// Remove some elements
cout << "Dequeued: " << cq.dequeue() << endl;
cout << "Dequeued: " << cq.dequeue() << endl;
cq.display();
// Add new elements (reusing space)
cq.enqueue(60);
cq.enqueue(70);
cq.display();
return 0;
}