《数据结构》--队列【各种实现，算法推荐】

🕗 发布于 2024-10-06 15:03 数据结构 算法 c++ C++ 后端

一、认识队列

队列是一种常见的数据结构，按照先进先出（FIFO，First In First Out）的原则排列数据。也就是说，最早进入队列的元素最先被移除。队列主要支持两种基本操作：

入队（enqueue）：将元素添加到队列的尾部。

出队（dequeue）：从队列的头部移除并返回元素。

队列的其他操作：

创建队列：初始化一个空队列。

查看队列头部元素：返回但不移除队列的头部元素（通常称为“peek”或“front”）。

判断队列是否为空：检查队列中是否还有元素。

获取队列大小：返回队列中元素的数量。

1.顺序队列

顺序队列即用顺序结构存储，数组实现：

#include <iostream>  

class Queue {  
private:  
    int* arr;  
    int front;  
    int rear;  
    int capacity;  
public:  
    Queue(int size) {  
        arr = new int[size];  
        capacity = size;  
        front = 0;  
        rear = -1;  
    }  

    ~Queue() {  
        delete[] arr;  
    }  

    void enqueue(int item) {  
        if (rear == capacity - 1) {  
            std::cout << "Queue is full!" << std::endl;  
            return;  
        }  
        arr[++rear] = item;  
    }  

    int dequeue() {  
        if (is_empty()) {  
            std::cout << "Queue is empty!" << std::endl;  
            return -1; // 或抛出异常  
        }  
        return arr[front++];  
    }  

    int peek() {  
        if (is_empty()) {  
            std::cout << "Queue is empty!" << std::endl;  
            return -1; // 或抛出异常  
        }  
        return arr[front];  
    }  

    bool is_empty() const {  
        return front > rear;  
    }  

    int size() const {  
        return rear - front + 1;  
    }  
};  

int main() {  
    Queue q(5);  

    q.enqueue(10);  
    q.enqueue(20);  
    q.enqueue(30);  

    std::cout << "Front element: " << q.peek() << std::endl; // 输出 10  

    std::cout << "Dequeued element: " << q.dequeue() << std::endl; // 输出 10  
    std::cout << "Queue size: " << q.size() << std::endl; // 输出 2  

    return 0;  
}

2.链式队列

链式队列即用链式存储，用链表实现：

#include <iostream>  

class Node {  
public:  
    int data;  
    Node* next;  

    Node(int value) : data(value), next(nullptr) {}  
};  

class Queue {  
private:  
    Node* front;  
    Node* rear;  
    int size;  
public:  
    Queue() : front(nullptr), rear(nullptr), size(0) {}  

    ~Queue() {  
        while (!is_empty()) {  
            dequeue();  
        }  
    }  

    void enqueue(int item) {  
        Node* newNode = new Node(item);  
        if (rear) {  
            rear->next = newNode;  
        }  
        rear = newNode;  
        if (!front) {  
            front = rear;  
        }  
        size++;  
    }  

    int dequeue() {  
        if (is_empty()) {  
            std::cout << "Queue is empty!" << std::endl;  
            return -1; // 或抛出异常  
        }  
        Node* temp = front;  
        int value = front->data;  
        front = front->next;  
        delete temp;  

        if (!front) {  
            rear = nullptr; // 队列变空  
        }  
        size--;  
        return value;  
    }  

    int peek() {  
        if (is_empty()) {  
            std::cout << "Queue is empty!" << std::endl;  
            return -1; // 或抛出异常  
        }  
        return front->data;  
    }  

    bool is_empty() const {  
        return size == 0;  
    }  

    int get_size() const {  
        return size;  
    }  
};  

int main() {  
    Queue q;  

    q.enqueue(10);  
    q.enqueue(20);  
    q.enqueue(30);  

    std::cout << "Front element: " << q.peek() << std::endl; // 输出 10  

    std::cout << "Dequeued element: " << q.dequeue() << std::endl; // 输出 10  
    std::cout << "Queue size: " << q.get_size() << std::endl; // 输出 2  

    return 0;  
}

二、双端队列

1.顺序双端队列

#include <iostream>  

class Deque {  
private:  
    int* arr;  
    int front;  
    int rear;  
    int capacity;  
public:  
    Deque(int size) {  
        arr = new int[size];  
        capacity = size;  
        front = -1;  
        rear = 0;  
    }  

    ~Deque() {  
        delete[] arr;  
    }  

    void insertFront(int item) {  
        if (is_full()) {  
            std::cout << "Deque is full!" << std::endl;  
            return;  
        }  
        if (is_empty()) {  
            front = 0;  
            rear = 0;  
        } else {  
            front = (front - 1 + capacity) % capacity; // 循环移动前指针  
        }  
        arr[front] = item;  
    }  

    void insertRear(int item) {  
        if (is_full()) {  
            std::cout << "Deque is full!" << std::endl;  
            return;  
        }  
        if (is_empty()) {  
            front = 0;  
            rear = 0;  
        } else {  
            rear = (rear + 1) % capacity; // 循环移动后指针  
        }  
        arr[rear] = item;  
    }  

    int deleteFront() {  
        if (is_empty()) {  
            std::cout << "Deque is empty!" << std::endl;  
            return -1; // 或抛出异常  
        }  
        int item = arr[front];  
        if (front == rear) { // 仅有一个元素  
            front = -1;  
            rear = 0;  
        } else {  
            front = (front + 1) % capacity; // 循环移动前指针  
        }  
        return item;  
    }  

    int deleteRear() {  
        if (is_empty()) {  
            std::cout << "Deque is empty!" << std::endl;  
            return -1; // 或抛出异常  
        }  
        int item = arr[rear];  
        if (front == rear) { // 仅有一个元素  
            front = -1;  
            rear = 0;  
        } else {  
            rear = (rear - 1 + capacity) % capacity; // 循环移动后指针  
        }  
        return item;  
    }  

    int getFront() const {  
        if (is_empty()) {  
            std::cout << "Deque is empty!" << std::endl;  
            return -1; // 或抛出异常  
        }  
        return arr[front];  
    }  

    int getRear() const {  
        if (is_empty()) {  
            std::cout << "Deque is empty!" << std::endl;  
            return -1; // 或抛出异常  
        }  
        return arr[rear];  
    }  

    bool is_empty() const {  
        return front == -1;  
    }  

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

int main() {  
    Deque dq(5);  

    dq.insertRear(10);  
    dq.insertRear(20);  
    dq.insertFront(5);  
    dq.insertFront(0);  

    std::cout << "Front element: " << dq.getFront() << std::endl; // 输出 0  
    std::cout << "Rear element: " << dq.getRear() << std::endl;   // 输出 20  

    dq.deleteFront(); // 删除 0  
    dq.deleteRear();  // 删除 20  

    std::cout << "Front element after deletions: " << dq.getFront() << std::endl; // 输出 5  

    return 0;  
}

2.链式双端队列

双端队列的链式存储，采用双向链表来实现模拟：

#include <iostream>  

class Node {  
public:  
    int data;  
    Node* next;  
    Node* prev;  
    
    Node(int value) : data(value), next(nullptr), prev(nullptr) {}  
};  

class Deque {  
private:  
    Node* front;  
    Node* rear;  
public:  
    Deque() : front(nullptr), rear(nullptr) {}  

    ~Deque() {  
        while (!is_empty()) {  
            deleteFront();  
        }  
    }  

    void insertFront(int item) {  
        Node* newNode = new Node(item);  
        if (is_empty()) {  
            front = rear = newNode;  
        } else {  
            newNode->next = front;  
            front->prev = newNode;  
            front = newNode;  
        }  
    }  

    void insertRear(int item) {  
        Node* newNode = new Node(item);  
        if (is_empty()) {  
            front = rear = newNode;  
        } else {  
            rear->next = newNode;  
            newNode->prev = rear;  
            rear = newNode;  
        }  
    }  

    int deleteFront() {  
        if (is_empty()) {  
            std::cout << "Deque is empty!" << std::endl;  
            return -1; // 或抛出异常  
        }  
        Node* temp = front;  
        int value = front->data;  
        front = front->next;  
        if (front) {  
            front->prev = nullptr;  
        } else {  
            rear = nullptr; // 如果队列变空  
        }  
        delete temp;  
        return value;  
    }  

    int deleteRear() {  
        if (is_empty()) {  
            std::cout << "Deque is empty!" << std::endl;  
            return -1; // 或抛出异常  
        }  
        Node* temp = rear;  
        int value = rear->data;  
        rear = rear->prev;  
        if (rear) {  
            rear->next = nullptr;  
        } else {  
            front = nullptr; // 如果队列变空  
        }  
        delete temp;  
        return value;  
    }  

    int getFront() const {  
        if (is_empty()) {  
            std::cout << "Deque is empty!" << std::endl;  
            return -1; // 或抛出异常  
        }  
        return front->data;  
    }  

    int getRear() const {  
        if (is_empty()) {  
            std::cout << "Deque is empty!" << std::endl;  
            return -1; // 或抛出异常  
        }  
        return rear->data;  
    }  

    bool is_empty() const {  
        return front == nullptr;  
    }  
};  

int main() {  
    Deque dq;  

    dq.insertRear(10);  
    dq.insertRear(20);  
    dq.insertFront(5);  
    dq.insertFront(0);  

    std::cout << "Front element: " << dq.getFront() << std::endl; // 输出 0  
    std::cout << "Rear element: " << dq.getRear() << std::endl;   // 输出 20  

    dq.deleteFront(); // 删除 0  
    dq.deleteRear();  // 删除 20  

    std::cout << "Front element after deletions: " << dq.getFront() << std::endl; // 输出 5  

    return 0;  
}

三、循环队列

1.顺序循环队列

#include <iostream>  

class CircularQueue {  
private:  
    int* arr;        // 存储队列元素的数组  
    int front;      // 队列头指针  
    int rear;       // 队列尾指针  
    int capacity;   // 队列的最大容量  
    int count;      // 当前队列中的元素数量  

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

    ~CircularQueue() {  
        delete[] arr;  
    }  

    // 入队操作  
    void enqueue(int item) {  
        if (is_full()) {  
            std::cout << "Queue is full!" << std::endl;  
            return;  
        }  
        rear = (rear + 1) % capacity; // 循环移动尾指针  
        arr[rear] = item;  
        count++;  
    }  

    // 出队操作  
    int dequeue() {  
        if (is_empty()) {  
            std::cout << "Queue is empty!" << std::endl;  
            return -1; // 或抛出异常  
        }  
        int item = arr[front];  
        front = (front + 1) % capacity; // 循环移动头指针  
        count--;  
        return item;  
    }  

    // 获取队头元素  
    int peek() const {  
        if (is_empty()) {  
            std::cout << "Queue is empty!" << std::endl;  
            return -1; // 或抛出异常  
        }  
        return arr[front];  
    }  

    // 检查队列是否为空  
    bool is_empty() const {  
        return count == 0;  
    }  

    // 检查队列是否已满  
    bool is_full() const {  
        return count == capacity;  
    }  

    // 获取当前队列大小  
    int size() const {  
        return count;  
    }  
};  

int main() {  
    CircularQueue cq(5); // 创建一个容量为5的循环队列  

    cq.enqueue(10);  
    cq.enqueue(20);  
    cq.enqueue(30);  
    cq.enqueue(40);  
    cq.enqueue(50);  

    std::cout << "Front element: " << cq.peek() << std::endl; // 输出 10  

    std::cout << "Dequeued: " << cq.dequeue() << std::endl; // 输出 10  
    std::cout << "Front element after dequeue: " << cq.peek() << std::endl; // 输出 20  

    cq.enqueue(60); // 尝试入队一个新元素  
    std::cout << "Front element after enqueue: " << cq.peek() << std::endl; // 输出 20  

    return 0;  
}

2.链式循环队列

采用循环链表的方式来实现循环队列

#include <iostream>  

class Node {  
public:  
    int data;  
    Node* next;  

    Node(int value) : data(value), next(nullptr) {}  
};  

class CircularQueue {  
private:  
    Node* front; // 队列头指针  
    Node* rear;  // 队列尾指针  
    int count;   // 当前队列中的元素数量  

public:  
    CircularQueue() : front(nullptr), rear(nullptr), count(0) {}  

    ~CircularQueue() {  
        while (!is_empty()) {  
            dequeue();  
        }  
    }  

    // 入队操作  
    void enqueue(int item) {  
        Node* newNode = new Node(item);  
        if (is_empty()) {  
            front = rear = newNode;  
            rear->next = front; // 形成循环  
        } else {  
            rear->next = newNode;  
            rear = newNode;  
            rear->next = front; // 形成循环  
        }  
        count++;  
    }  

    // 出队操作  
    int dequeue() {  
        if (is_empty()) {  
            std::cout << "Queue is empty!" << std::endl;  
            return -1; // 或抛出异常  
        }  
        int item = front->data;  
        Node* temp = front;  
        if (front == rear) { // 只有一个元素  
            front = rear = nullptr;  
        } else {  
            front = front->next;  
            rear->next = front; // 更新尾指针  
        }  
        delete temp;  
        count--;  
        return item;  
    }  

    // 获取队头元素  
    int peek() const {  
        if (is_empty()) {  
            std::cout << "Queue is empty!" << std::endl;  
            return -1; // 或抛出异常  
        }  
        return front->data;  
    }  

    // 检查队列是否为空  
    bool is_empty() const {  
        return count == 0;  
    }  

    // 获取当前队列大小  
    int size() const {  
        return count;  
    }  
};  

int main() {  
    CircularQueue cq; // 创建一个循环队列  

    cq.enqueue(10);  
    cq.enqueue(20);  
    cq.enqueue(30);  

    std::cout << "Front element: " << cq.peek() << std::endl; // 输出 10  

    std::cout << "Dequeued: " << cq.dequeue() << std::endl; // 输出 10  
    std::cout << "Front element after dequeue: " << cq.peek() << std::endl; // 输出 20  

    cq.enqueue(40); // 尝试入队一个新元素  
    std::cout << "Front element after enqueue: " << cq.peek() << std::endl; // 输出 20  

    return 0;  
}

四、算法专题

队列是一种重要的数据结构，广泛应用于计算机科学的各个领域。理解队列的基本概念、操作和实现方式对于学习数据结构和算法非常重要。

1.队列的应用场景

任务调度：操作系统中的进程调度。

打印队列：管理打印任务的顺序。

广度优先搜索（BFS）：图算法中的节点访问顺序。

消息队列：在分布式系统中传递消息。

2.队列的相关算法

循环队列：通过循环数组或链表实现，避免了空间浪费。

优先队列：每个元素都有一个优先级，出队时优先级高的元素先被移除。

阻塞队列：在多线程环境中使用，支持线程安全的入队和出队操作。

3.算法题推荐

模拟队列：232. 用栈实现队列 - 力扣（LeetCode）

class MyQueue {
stack<int> v;
public:
MyQueue() {

}
void push(int x) {
v.push(x);
}
int pop() {
if(empty())return NULL;
stack<int> ts;
while (!v.empty()) {
ts.push(v.top());
v.pop();
}
int ans = ts.top();
ts.pop();
while (!ts.empty()) {
v.push(ts.top());
ts.pop();
}
return ans;
}
int peek() {
if(empty())return NULL;
stack<int> ts = v;
while (ts.size() != 1) {
ts.pop();
}//就剩栈底了
return ts.top();
}
bool empty() {
return v.empty();
}
};

/**
 * Your MyQueue object will be instantiated and called as such:
 * MyQueue* obj = new MyQueue();
 * obj->push(x);
 * int param_2 = obj->pop();
 * int param_3 = obj->peek();
 * bool param_4 = obj->empty();
 */

239. 滑动窗口最大值 - 力扣（LeetCode）双端队列：239. 滑动窗口最大值 - 力扣（LeetCode）

class Solution {
public:
    //时间复杂度：O((n-k)*k)
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
vector<int> ret;
if (nums.size() == 0)return ret;

deque<int> q; //存储位置
for (int i = 0; i < nums.size(); i++) {
while (!q.empty() && nums[i] > nums[q.back()]) {
q.pop_back();
}
q.push_back(i);
if (k == i - q.front()) q.pop_front();//超出长度
if (i >= k - 1) ret.push_back(nums[q.front()]);
}
return ret;
    }
};

优先队列(堆)：23. 合并 K 个升序链表 - 力扣（LeetCode）

class Solution {
public:
    struct Status {
        int val;
        ListNode *ptr;
        bool operator < (const Status &rhs) const {
            return val > rhs.val;
        }
    };

    priority_queue <Status> q;

    ListNode* mergeKLists(vector<ListNode*>& lists) {
        for (auto node: lists) {
            if (node) q.push({node->val, node});
        }
        ListNode head, *tail = &head;
        while (!q.empty()) {
            auto f = q.top(); q.pop();
            tail->next = f.ptr; 
            tail = tail->next;
            if (f.ptr->next) q.push({f.ptr->next->val, f.ptr->next});
        }
        return head.next;
    }
};

感谢大家！

原文地址：https://blog.csdn.net/U2396573637/article/details/142725771

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！

上一篇：LLM大模型学习精要系列(一)：掌握基础，开启大模型之旅
下一篇：LeetCode78 子集

原码、反码、补码极简理解
原码、反码、补码极简理解
阅读更多2024-10-07
Luminar财务造假风波：激光雷达龙头的困境与挑战
带着对Luminar财务造假事件的疑问，笔者查阅了该公司的往期财报，尝试从中找出一些“蛛丝马迹”。在过去的几个季度里，Luminar向Scale AI支付了超过3500万美元的数据标注服务费，而Sca
阅读更多2024-10-07
科研必备语料库
科研必备语料库
阅读更多2024-10-07
网络威胁情报技术的进步
本指南深入探讨了 CTI 的最新进展，让您了解这些技术如何彻底改变打击网络犯罪的方式。
阅读更多2024-10-07
Queue、Hashtable
对于引用类型：equal比较的是两个对象的地址是否相同；对于值类型：equal是比较对象的值，就像struct是值类型，equal就是比较他的成员的值是否相等。gethashcode怎么算的不用管，只
阅读更多2024-10-07
防反接电路设计
串联二极管，优点：成本低、设计简单缺点：损耗大，P = ui。
阅读更多2024-10-07
如何在 MySQL 中实现数据压缩
在 MySQL 中实现数据压缩可以有效地节省存储空间和提高数据传输效率。可以通过表压缩、数据备份压缩和通信压缩等方法来实现数据压缩。在启用数据压缩之前，需要评估对系统性能的影响，选择适合的数据压缩方法
阅读更多2024-10-07
【黑马点评】使用RabbitMQ实现消息队列——1.Docker与RabbitMQ环境安装
黑马点评中使用RabbitMQ实现消息队列
阅读更多2024-10-07
短线程序化交易采用限价单进场历史回测还需要设置滑点吗？
短线程序化交易限价单进场时，历史回测设滑点很重要，可模拟真实交易成本、测试策略稳健性，不同市场品种滑点不同，合理设置滑点能评估策略盈利与适应能力。
阅读更多2024-10-07
对 LLM 工具使用进行统一
尽管还留了一点小尾巴，但我们认为相比以前，情况已经有了很大的改进，之前的工具调用方式分散、混乱且记录不足。我们希望我们为统一作的努力可以让开源开发人员更轻松地在他们的项目中使用工具，以通过一系列令人惊
阅读更多2024-10-07