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

news/2024/10/6 18:00:08 标签: 数据结构, 算法, 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;
    }
};

感谢大家！ 


http://www.niftyadmin.cn/n/5691966.html

相关文章

ElasticSearch备考 -- Multi match

ElasticSearch备考 -- Multi match

一、题目 索引task有3个字段a、b、c&#xff0c;写一个查询去匹配这三个字段为mom&#xff0c;其中b的字段评分比a、c字段大一倍&#xff0c;将他们的分数相加作为最后的总分数 二、思考 通过题目要求对多个字段进行匹配查询&#xff0c;可以考虑multi match、bool query操作。…
阅读更多...
结合大语言模型的机械臂抓取操作简单介绍

结合大语言模型的机械臂抓取操作简单介绍

一、大语言模型与机械臂抓取的基本操作 1. 大语言模型简介 大语言模型是基于深度学习技术构建的自然语言处理模型&#xff0c;能够生成、理解和处理文本信息。这些模型通过训练大量的文本数据&#xff0c;学习语法、上下文和常识&#xff0c;能够执行多种任务&#xff0c;如文…
阅读更多...
涂色问题 乘法原理（2024CCPC 山东省赛 C）

涂色问题 乘法原理（2024CCPC 山东省赛 C）

//*下午打得脑子连着眼睛一起疼 很多很基础的题目都没有做出来&#xff0c;规律题也找得很慢。比如下面这题&#xff0c;一定要多做&#xff0c;下次看到就直接写。 原题链接&#xff1a;https://codeforces.com/group/w6iGs8kreW/contest/555584/problem/C C. Colorful Segm…
阅读更多...
如何在 SQL 中创建一个新的数据库？

如何在 SQL 中创建一个新的数据库？

在SQL中创建一个新的数据库&#xff0c;首先你需要有一个可以执行SQL语句的环境。 这通常意味着你已经有了一个数据库管理系统&#xff08;DBMS&#xff09;&#xff0c;如MySQL、PostgreSQL、Oracle或Microsoft SQL Server等。 不同的DBMS可能有不同的细节&#xff0c;但基本…
阅读更多...
每日读则推(五)——Rose

每日读则推(五)——Rose

n/v. 照顾 n.护理 We sponsored the care these dogs needed and most of them found forever homes! One n.赞助者,赞助商 v.赞助(活动、节目等),为慈善活动捐资 lovely senior, Rose, is still waiting for hers. Shes mostly blind and needs eye medication, …
阅读更多...
讯飞星火编排创建智能体学习（五）：变量和文本拼接

讯飞星火编排创建智能体学习（五）：变量和文本拼接

引言 在讯飞星火编排创建智能体学习&#xff08;四&#xff09;&#xff1a;网页读取-CSDN博客中&#xff0c;我介绍了如何用网页读取功能从网上搜索车次信息。其中&#xff0c;我使用用大模型节点从文本中提取车次并合成了所需要的URL&#xff0c;今天介绍一下如何用变量和文…
阅读更多...
k8s的简介和部署

k8s的简介和部署

一、k8s简介 在部署应用程序的方式上面&#xff0c;主要经历了三个阶段&#xff1a; 传统部署:互联网早期&#xff0c;会直接将应用程序部署在物理机上优点:简单&#xff0c;不需要其它技术的参与缺点:不能为应用程序定义资源使用边界&#xff0c;很难合理地分配计算资源&…
阅读更多...
简单认识 redis -3 -其他命令

简单认识 redis -3 -其他命令

一.Redis HyperLogLog Redis HyperLogLog 是用来做基数统计的算法&#xff0c;HyperLogLog 的优点是&#xff0c;在输入元素的数量或者体积非常非常大时&#xff0c;计算基数所需的空间总是固定 的、并且是很小的。每个 HyperLogLog 键只需要花费 12 KB 内存&#xff0c;就可以…
阅读更多...
最新文章

Copyright @ 2022~2023