数据结构：队列的了解与示例（CPU处理任务的时间）

90 阅读 0 评论 60 点赞

我是靠谱客的博主愉快招牌，最近开发中收集的这篇文章主要介绍数据结构：队列的了解与示例（CPU处理任务的时间），觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

使用数组来模拟队列
CPU模拟调度所有任务，总共n个任务，每个任务处理时间不同，最多处理t（时间片），如果t时间没有处理完毕
就把该任务移动到所有任务的后面
如果我们使用平时常用的队列，那么随着数据的不断进出，将出现溢出的现象
所以我们把数组形成一个环形的缓冲区，就是一维数组形成一个圆圈，另外我们为了区分队列的空和满，我们规定头和尾之间至少有一个空位

#include <iostream>

#define LEN 1000

using namespace std;

//任务结构体:任务名称和需要处理的时间
typedef struct pp
{
    char name[50];
    int t;
} P;

P Q[LEN];//定义一个任务队列
int head,tail,n;


//当头,尾的索引超过最大值的时候就置零（取模）
//入队列
void enqueue(P x)
{
    Q[tail]=x;
    tail=(tail+1)%LEN;
}
//出队列（返回任务）
P dequeue()
{
    P x=Q[head];
    head=(head+1)%LEN;
    return x;
}


int main()
{
    int elapse=0;//CPU总耗时
    int min_t;//CPU处理时间为两者最小时间
    P myQ;

    printf("请输入有多少个任务？n");
    scanf("%d",&n);

    printf("请分别输入任务名称和需要运行的时间n");
    //将所有任务添加至队列
    for(int i=0; i<n; i++)
    {
        scanf("%s %d",Q[i].name,&Q[i].t);
        //scanf("%d",&Q[i].t);
    }
    head=0;
    tail=n;

    while(head!=tail)
    {
        myQ=dequeue();
        min_t=min(100,myQ.t);//时间片设定为100ms,
        myQ.t-=min_t;//剩余时间
        elapse+=min_t;//总共已处理的时间

        //未处理完的重新添加到队列
        if(myQ.t>0)
        {
            enqueue(myQ);
        }
        else
        {
            printf("%s 已用时间：%dmsn",myQ.name,elapse);
        }
    }
    cout << "任务完成！" << endl;
    return 0;
}

下面使用标准库里面的队列，来实现上述CPU对任务队列的处理

#include <iostream>
#include<queue>

using namespace std;

int main()
{
    string name;
    int n,t;

    queue<pair<string,int>> Q;//任务队列

    printf("请输入有多少个任务？n");
    cin>>n;
    printf("请分别输入任务名称和需要运行的时间n");
    for(int i=0; i<n; i++)
    {
        cin>>name>>t;
        Q.push(make_pair(name,t));
    }
    //pair保存成对数据的结构体模板
    pair<string,int> myQ;//myQ.first是任务名称，myQ.second是任务运行时间
    int elapse=0;
    int min_t;
    while(!Q.empty())
    {
        myQ=Q.front();
        Q.pop();
        min_t=min(myQ.second,100);//运行时间
        myQ.second-=min_t;//剩余时间
        elapse+=min_t;//总耗时
        if(myQ.second>0)
        {
            Q.push(myQ);
        }
        else
        {
            cout<<myQ.first<<" 运行时间"<<elapse<<endl;
        }
    }
    cout << "任务完成！" << endl;
    return 0;
}