UVa210 双端队列deque_uva 210-CSDN博客

本文链接：https://blog.csdn.net/peterchen96/article/details/79255781

该博客详细介绍了如何利用双端队列（deque）解决UVa210的编程问题。deque在首尾两端都支持插入和删除操作，适合用作执行队列。在程序中，当读入n段程序后，将1到n依次压入执行队列。当执行队列不为空时，会持续执行程序。如果分配的时间未用完，会继续执行当前程序。遇到lock指令时，会根据情况进行处理，如设置lockflag或把当前程序移出执行队列。文章还提及了将字符串中的数字转换为int类型的方法。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

采用数据结构与大概流程

Deque：支持在首尾两端插入和删除
阻止队列：queue，只需要从后部插入前端取出
执行队列：因为需要从前端插入，所以采用deque
1.读入n段程序，将1-n压入执行队列中
2.如果执行队列不空时一直执行程序
3.当分配时间没用完时始终执行当前程序
4.执行不同指令
将字符串中数字转变为int型的方法：
int a=stoi(string.substr(string.find_first_of("0123456789"))
当第一次遇到lock时，将lockflag置为1，非第一次遇到lock时加入组织队列，执行队列的这一段程序弹出（注意将分配时间置为零）。

代码实现

#include<iostream>
#include<queue>
#include<string>
#include<deque>
#include<fstream>
using namespace std;        
int main()
{
    //ofstream fileout("data.txt");
    int N=1;
    cin >> N;
    //cout << endl;
    for (int j = 0; j < N; j++)
    {
        int n, t1, t2, t3, t4, t5, q;
        cin >> n >> t1 >> t2 >> t3 >> t4 >> t5 >> q;
        getchar();
        queue<string> *program = new queue<string>[n + 1];
        deque<int> wait;
        queue<int> block;
        int alpha[26] = {0};
        //输入
        for (int i = 1; i <= n; i++)
        {
            string input;
            while (getline(cin, input))
            {
                program[i].push(input);
                if (input == "end")
                    break;
            }
        }
        /*for (int i = 1; i <= n; i++)
        {
        while (!program[i].empty())
        {
        cout << program[i].front()<<endl;
        program[i].pop();
        }
        cout << endl;
        }*/
        //把program映射为数字
        for (int i = 1; i <= n; i++)
        {
            wait.push_back(i);
        }
        //处理
        int lockflag = 0;
        int flag = 1;
        while (!wait.empty())
        {
            int num = wait.front();
            wait.pop_front();
            string excute;
            int runtime = q;
            while (runtime > 0)
            {
                excute = program[num].front();
                //cout << num<<"."<<excute << endl;
                if (excute[2]=='=')
                {
                    //转化数字
                    alpha[excute[0] - 'a'] = stoi(excute.substr(excute.find_first_of("0123456789")));
                    //cout << alpha[excute[0] - 'a'];
                    program[num].pop();
                    runtime = runtime - t1;
                }
                else if (excute[2]=='i')
                {
                    cout << num << ": " << alpha[*excute.rbegin() - 'a'] << endl;
                    //fileout << num << ": " << alpha[*excute.rbegin() - 'a'] << endl;
                    program[num].pop();
                    runtime = runtime - t2;
                }
                else if (excute[2] == 'c')//lock
                {
                    if (lockflag == 0)
                    {
                        lockflag = 1;
                        runtime = runtime - t3;
                        program[num].pop();
                    }
                    else
                    {
                        runtime = 0;
                        block.push(num);
                        flag = 0;
                    }
                }
                else if (excute[2] == 'l')
                {
                    lockflag = 0;
                    runtime = runtime - t4;
                    if (!block.empty())
                    {
                        wait.push_front(block.front());
                        block.pop();
                    }
                    program[num].pop();
                }
                else //end
                {
                    runtime = 0;
                    flag = 0;
                }
            }
            if (flag == 0) //end case
            {
                flag = 1;
            }
            else
            {
                wait.push_back(num);
            }
            //if(!wait.empty())     cout << wait.front() << endl;
            //cout << lockflag << endl;
        }
        if(j!=N-1)
            cout << endl;
        //fileout << endl;
    }
    //fileout.close();
    system("pause");
    return 0;
}