队列

天之神_复仇者_ZDZC

2025-10-10 16:32:57

发布于：浙江

0阅读

0回复

0点赞

队列的基本概念
特性
先进先出(FIFO)：最先进入的元素最先出队

两端操作：只能在一端(队尾)添加，在另一端(队头)删除

顺序存取：元素按进入顺序存储和访问

C++ 中的队列实现
2.1 std::queue (标准库队列)
cpp
#include <queue>
#include <iostream>

using namespace std;

int main() {
// 创建队列
queue<int> q;

// 入队操作
q.push(10);
q.push(20);
q.push(30);

// 访问队首和队尾
cout << "队首元素: " << q.front() << endl;  // 10
cout << "队尾元素: " << q.back() << endl;   // 30

// 出队操作
q.pop();  // 移除10
cout << "出队后队首: " << q.front() << endl;  // 20

// 其他操作
cout << "队列大小: " << q.size() << endl;    // 2
cout << "是否为空: " << q.empty() << endl;   // 0(false)

return 0;

}
2.2 基于数组的循环队列
cpp
#include <iostream>
using namespace std;

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

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

~CircularQueue() {
    delete[] arr;
}

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

bool isEmpty() {
    return front == -1;
}

void enqueue(int value) {
    if (isFull()) {
        cout << "队列已满!" << endl;
        return;
    }
    
    if (isEmpty()) {
        front = rear = 0;
    } else {
        rear = (rear + 1) % capacity;
    }
    arr[rear] = value;
}

int dequeue() {
    if (isEmpty()) {
        cout << "队列为空!" << endl;
        return -1;
    }
    
    int value = arr[front];
    if (front == rear) {
        front = rear = -1;
    } else {
        front = (front + 1) % capacity;
    }
    return value;
}

int getFront() {
    if (isEmpty()) {
        return -1;
    }
    return arr[front];
}

void display() {
    if (isEmpty()) {
        cout << "队列为空" << endl;
        return;
    }
    
    cout << "队列元素: ";
    int i = front;
    while (true) {
        cout << arr[i] << " ";
        if (i == rear) break;
        i = (i + 1) % capacity;
    }
    cout << endl;
}

};

// 使用示例
int main() {
CircularQueue cq(5);
cq.enqueue(1);
cq.enqueue(2);
cq.enqueue(3);
cq.display(); // 输出: 1 2 3

cq.dequeue();
cq.display();  // 输出: 2 3

return 0;

}
2.3 基于链表的队列
cpp
#include <iostream>
using namespace std;

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

class LinkedListQueue {
private:
Node *front, *rear;

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

~LinkedListQueue() {
    while (!isEmpty()) {
        dequeue();
    }
}

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

void enqueue(int value) {
    Node* newNode = new Node(value);
    if (rear == nullptr) {
        front = rear = newNode;
    } else {
        rear->next = newNode;
        rear = newNode;
    }
}

int dequeue() {
    if (isEmpty()) {
        cout << "队列为空!" << endl;
        return -1;
    }
    
    Node* temp = front;
    int value = temp->data;
    front = front->next;
    
    if (front == nullptr) {
        rear = nullptr;
    }
    
    delete temp;
    return value;
}

int getFront() {
    if (isEmpty()) {
        return -1;
    }
    return front->data;
}

void display() {
    if (isEmpty()) {
        cout << "队列为空" << endl;
        return;
    }
    
    cout << "队列元素: ";
    Node* current = front;
    while (current != nullptr) {
        cout << current->data << " ";
        current = current->next;
    }
    cout << endl;
}

};
3. 不同类型的队列
3.1 std::priority_queue (优先队列)
cpp
#include <queue>
#include <iostream>
using namespace std;

int main() {
// 最大堆（默认）
priority_queue<int> maxHeap;

// 最小堆
priority_queue<int, vector<int>, greater<int>> minHeap;

maxHeap.push(30);
maxHeap.push(10);
maxHeap.push(20);

cout << "最大堆顶部: " << maxHeap.top() << endl;  // 30

minHeap.push(30);
minHeap.push(10);
minHeap.push(20);

cout << "最小堆顶部: " << minHeap.top() << endl;  // 10

return 0;

}
3.2 std::deque (双端队列)
cpp
#include <deque>
#include <iostream>
using namespace std;

int main() {
deque<int> dq;

// 两端操作
dq.push_back(10);   // 尾部添加
dq.push_front(5);   // 头部添加
dq.push_back(15);

cout << "双端队列: ";
for (int num : dq) {
    cout << num << " ";  // 5 10 15
}
cout << endl;

dq.pop_front();  // 头部删除
dq.pop_back();   // 尾部删除

return 0;

}
4. 队列的常用操作汇总
std::queue 主要成员函数
函数说明时间复杂度
push(value) 入队 O(1)
pop() 出队 O(1)
front() 访问队首 O(1)
back() 访问队尾 O(1)
empty() 判断空 O(1)
size() 获取大小 O(1)
5. 实际应用场景
5.1 广度优先搜索(BFS)
cpp
#include <queue>
#include <vector>
using namespace std;

void BFS(vector<vector<int>>& graph, int start) {
vector<bool> visited(graph.size(), false);
queue<int> q;

q.push(start);
visited[start] = true;

while (!q.empty()) {
    int current = q.front();
    q.pop();
    
    cout << "访问节点: " << current << endl;
    
    for (int neighbor : graph[current]) {
        if (!visited[neighbor]) {
            visited[neighbor] = true;
            q.push(neighbor);
        }
    }
}

}
5.2 任务调度系统
cpp
#include <queue>
#include <string>
#include <iostream>
using namespace std;

struct Task {
string name;
int priority;

Task(string n, int p) : name(n), priority(p) {}

};

class TaskScheduler {
private:
queue<Task> taskQueue;

public:
void addTask(const string& name, int priority = 0) {
taskQueue.push(Task(name, priority));
}

void processTasks() {
    while (!taskQueue.empty()) {
        Task current = taskQueue.front();
        taskQueue.pop();
        cout << "处理任务: " << current.name << endl;
    }
}

};
6. 性能比较
队列类型插入性能删除性能空间复杂度适用场景
stdqueue O(1) O(1) O(n) 一般队列操作
循环队列 O(1) O(1) O(n) 固定大小队列
链表队列 O(1) O(1) O(n) 动态大小队列
优先队列 O(log n) O(log n) O(n) 需要优先级
7. 选择指南
普通FIFO需求：使用 stdqueue

需要两端操作：使用 std::deque

优先级处理：使用 std::priority_queue

固定大小优化：使用循环队列

动态大小：使用链表队列

有帮助，赞一个