Algorithms & Data Structures : Queue Problems

Problem

LeetCode 346. Moving Average from Data Stream

LeetCode : 1429. First Unique Number
[queue][hash table]

LeetCode : 2073. Time Needed to Buy Tickets
[queue][Array]

— — —

LeetCode 1696. Jump Game VI
[monotonic queue]

LeetCode 346. Moving Average from Data Stream

class MovingAverage {
public:
    /** Initialize your data structure here. */
    
    queue<int> q;
    int q_size = 0;
    int nowSum = 0;
    MovingAverage(int size) {
        q_size = size;
    }
    
    double next(int val) {
        if(q.size() < q_size) {
            nowSum += val;
            q.push(val);
        } else if(q.size() == q_size) {
            nowSum -= q.front();
            nowSum += val;
            q.pop();
            q.push(val);
        }
        
        return (double)nowSum / q.size();
    }
};

LeetCode : 1429. First Unique Number

class FirstUnique {
public:
    unordered_map <int, int> um;
    queue<int> q;
    
    FirstUnique(vector<int>& nums) {
        for(int i = 0;i < nums.size();i++) {
            um[nums[i]]++;
        }        
        for(int i = 0;i < nums.size();i++) {
            if(1 == um[nums[i]]) {
                q.push(nums[i]);
            }
        }
    }
    
    int showFirstUnique() {
        if(q.empty()) {
            return -1;
        }
        
        while(um[q.front()] > 1) {
            q.pop();
        }
        
        if(q.empty()) {
            return -1;
        }
        
        return q.front();
    }
    
    void add(int value) {
        if(um.find(value) == um.end()) {
            q.push(value);
        }
        um[value]++;
    }
};
/**
 * Your FirstUnique object will be instantiated and called as such:
 * FirstUnique* obj = new FirstUnique(nums);
 * int param_1 = obj->showFirstUnique();
 * obj->add(value);
 */

LeetCode : 2073. Time Needed to Buy Tickets

class Solution {
public:
    int timeRequiredToBuy(vector<int>& tickets, int k) {
        queue<int> q;
        int t = 0;
        for(int i = 0;i < tickets.size();i++) {
            q.push(i);
        }
        while(tickets[k] != 0) {
            int nowp = q.front();
            q.pop();
            tickets[nowp]--;
            if(tickets[nowp] != 0) {
                q.push(nowp);
            }
            t++;
        }
        return t;
    }
};