2.queue.md

队列和线程池

队列的基本操作：入队，出队

对应着插入，删除

队列是一种队尾进队首出的数据结构，先进先出

队列的删除

头指针后移，注意长度不变（因为在再次插入的时候是会 % 队列的长度，就自动填上被删除的节点了，相当于被更新了）

队列的插入

尾指针后移，其余不变

队列的假溢出

队列虽然尾指针到了队列长度的位置，但是队列不是真的满了。还有空着的位置

为了解决这种问题，有了循环队列的诞生。（走到tail了再指向队列的头）（其实就是 % 长度）

注意一般情况下尾指针都是指向最后一个元素的下一位的

因为在绝大多数语言当中队列的区间都是左闭右开的，即[,)

这样的好处是tail - head即为队列的长度

下面实现一个简单的队列

class Queue {
public :
    Queue(int n = 10) : arr(n), head(0), tail(0) {}
    void push(int x) {
        if (full()) {
            cout << "queue full" << endl;
            return ;
        }
        arr[tail] = x;
        tail += 1;
        return ;
    }
    void pop() {
        if (empty()) {
            head += 1;
        }
    }
    bool empty() {
        return head == tail;
    }
    bool full() {
        return tail == arr.size();
    }
    int front() {
        if (empty()) return 0;
        return arr[head];
    }
    int size() {
        return tail - head;
    }
    void output() {
        cout << "Queue : ";
        for (int i = head; i < tail; i++) {
            cout << arr[i] << " ";
        }
        cout << endl;
    }
private :
    int head, tail;
    vector<int> arr;
};

int main() {
    string op;
    int value;
    Queue q(5);
    while (cin >> op) {
        if (op == "insert") {
        cin >> value;
        q.push(value);
        } else if (op == "front") {
        cout << "front element : " << q.front() << endl;
        } else if (op == "pop") {
            q.pop();
        } else if (op == "size") {
            cout << "queue size : " << q.size() << endl;
        }
        // 具有五个基本的功能，入队，出队，判空/满，查看元素数量，查看队首元素
    q.output();
    }
    return 0;
}

下面在队列的基础上实现一个循环队列

要解决的问题：1.循环起来 2.长度如何判断

方案：

1. 设置一个cnt来记录元素数量
2. 在push和pop的时候判断头和尾是否为空
3. 每次push和pop更新cnt的值
4. 判空和判满操作比较cnt和0，cnt和arr.size()的值
5. 修改output

class Queue {
public :
    Queue(int n = 10) : arr(n), head(0), tail(0), cnt(0) {}
    void push(int x) {
        if (full()) {
            cout << "queue full" << endl;
            return ;
        }
        arr[tail] = x;
        tail += 1;
        cnt += 1;
        if (tail == arr.size()) tail = 0;
        return ;
    }
    void pop() {
        if (empty()) {
            return ;
        }
        head += 1;
        cnt -= 1;
        if (head == arr.size()) head = 0;
        return ;
    }
    bool empty() {
        return cnt == 0;
    }
    bool full() {
        return cnt == arr.size();
    }
    int front() {
        if (empty()) return 0;
        return arr[head];
    }
    int size() {
        return cnt;
    }
    void output() {
        cout << "Queue : ";
        for (int i = 0, j = head; i < cnt; i++) {
            cout << arr[j] << " ";
            j += 1;
            if (j == arr.size()) j = 0;
        }
        cout << endl;
    }
private :
    int head, tail;
    int cnt;
    // cnt为当前元素数量
    vector<int> arr;
};

int main() {
    string op;
    int value;
    Queue q(5);
    while (cin >> op) {
        if (op == "insert") {
        cin >> value;
        q.push(value);
        } else if (op == "front") {
        cout << "front element : " << q.front() << endl;
        } else if (op == "pop") {
            q.pop();
        } else if (op == "size") {
            cout << "queue size : " << q.size() << endl;
        }
    q.output();
    }
    return 0;
}

队列的应用

场景一：CPU的超线程技术

两个核心（任务处理单元），一个核心有一个任务处理队列

但是此时对外表现也是两个任务处理队列

如果应用了超线程处理技术

对外表现就是四个任务处理队列，用户就会认为是四核，也就是平时所说的双核四线程

但是企业级的CPU一般是多路的，一路就是一个CPU

所以核心->CPU->多路 是一个递增的概念

线程池的任务队列

一个进程是可以包含多个线程的

但是以往的线程模型是需要一个申请一个，对线程进行频繁的申请和销毁

这样对系统资源是极大的浪费

引入线程池模型

由线程池类管理若干个线程，从任务队列中取计算任务

任务队列就像一个缓冲区