算法与数据结构基础

队列基础

队列具有“先进先出”的特点，用这个特点我们可以用它来处理时间序列相关或先后次序相关的问题，例如 LeetCode题目 933. Number of Recent Calls，时间复杂度O(1)：

//933. Number of Recent Calls

private queue<int> q;

public int ping(int t) {

        q.push(t);

        while(q.front()<t-) q.pop();

        return q.size();

    }

尝试用queue求解这样一个问题：假设某服务对单个IP限制访问1000次/min，输入为ip、TimeStamp；返回为bool，超过限制返回false，否则返回true。

相关LeetCode题：

933. Number of Recent Calls 题解

346. Moving Average from Data Stream 题解

622. Design Circular Queue 题解

队列应用于BFS

也常常应用队列先进先出的特性，模拟广度优先搜索(BFS)过程，例如 LeetCode题目 582. Kill Process，时间复杂度O(n)：

//582. Kill Process

class Solution {

public:

    vector<int> killProcess(vector<int>& pid, vector<int>& ppid, int kill) {

        vector<int> res;

        unordered_map<int,unordered_set<int>> m;

        for(int i=;i<pid.size();i++) m[ppid[i]].insert(pid[i]);

        queue<int> q;

        q.push(kill);

        while(!q.empty()){

            int p=q.front();q.pop();

            res.push_back(p);

            for(auto child:m[p]) q.push(child);

        }

        return res;

    }

};

巴特西

算法与数据结构基础 - 队列(Queue)

最新文章

热门文章