c++ - 使用结构的队列(出租车调度问题)

Question

我想编写从用户读取命令的程序，当 d is enter a Taxi is enter, it prompt enter driver_id并将出租车存储在队列中(队列最多可以有 n 辆出租车)，当命令 c 时由客户输入，它将队列中最早的出租车分配给客户。
我正在尝试使用 struct 成员函数来解决它，以便我们的代码看起来不错，但是尽管我已经初始化了 n=4 ，只能存储2出租车，并告诉我第三个条目的队列已满，这不应该发生。请检查我的方法。
程序运行如下:

PS C:\Users; if ($?) { g++struct_taxi};; if ($?) { .\struct_taxi}

enter command:d

enter driverid:122

enter command:d

enter driverid:124

enter command:d

enter driverid:126

Q is full    

代码:

#include<iostream>
using namespace std;
const int n=4;
struct Queue{
int elements[n],nwaiting,front;
void initialize(){
    nwaiting=0;
    front=0;

}
bool insert(int v){
    if(nwaiting>=n)
        return false;
    elements[(front+nwaiting)%n]=v;
    nwaiting++;
    return true;
}
bool remove(int &v){
    if(nwaiting==0)
        return false;
    else{
        v=elements[front];
        front=(front+1)%n;
        nwaiting--;
        return true;
    }
    
}
};
int main(){
Queue q;
q.initialize();
while(true){
cout<<"enter command:";
char c;cin>>c;
if(c=='d'){
    cout<<"enter driverid:";
    int driverid;cin>>driverid;
    if(!q.insert(driverid)){
        cout<<"Q is full\n";}
    else{
        q.insert(driverid);
    }


}
else if(c=='c'){
    int driverid;
    if(!q.remove(driverid)){
        cout<<"No taxi available.\n";
    }
    else
        //q.remove(driverid); 
        cout<<"assigning:"<<" "<<driverid<<endl;
             
}
}
}

Answer 1

问题是当你检查条件if(!q.insert(driverid)) ，您已经将该驱动程序插入系统。然后是else语句用 q.insert(driverid); 再插入一次
所以解决方案是简单地删除else陈述。

#include<iostream>
using namespace std;
const int n=4;

struct Queue
{
    int elements[n],nwaiting,front;
    void initialize()
    {
        nwaiting=0;
        front=0;

    }
    bool insert(int v)
    {
        if(nwaiting>=n) {return false;}
        elements[(front+nwaiting)%n]=v;
        nwaiting++;
        return true;
    }
    bool remove(int &v)
    {
        if(nwaiting==0)
            return false;
        else
        {
            v=elements[front];
            front=(front+1)%n;
            nwaiting--;
            return true;
        }

    }
};
int main()
{
    Queue q;
    q.initialize();
    while(true)
    {
        cout<<"enter command:";
        char c;
        cin>>c;
        if(c=='d')
        {
            cout<<"enter driverid:";
            int driverid;
            cin>>driverid;
            if(!q.insert(driverid))
            {
                cout<<"Q is full\n";
            }
        }
        else if(c=='c')
        {
            int driverid;
            if(!q.remove(driverid))
            {
                cout<<"No taxi available.\n";
            }
            else {cout<<"assigning:"<<" "<<driverid<<endl;}
        }
    }
}

结果:

enter command:d
enter driverid:121
enter command:d
enter driverid:122
enter command:d
enter driverid:123
enter command:d
enter driverid:124
enter command:d
enter driverid:125
Q is full

显然更简单的方法是使用 std::queue ，一种用于这种情况的数据结构，并且具有与您的 Queue 相同的功能struct，代码会短得多:

#include <iostream>
#include <queue>
using namespace std;
const int maxn=2;



int main()
{   queue<int> q;
    while(true)
    {
        cout << "Enter command : "; char c; cin >> c;
        if (c == 'd') //if inserting new driver
        {
            cout << "Enter driver's ID : "; int id; cin >> id; //input id
            if (q.size() == maxn) {cout << "Queue is full\n";} //if size of queue is equal to maxn, no insert
            else {q.push(id);} //else insert
        }
        else if (c == 'c')
        {
            if (q.empty()) {cout << "No driver available\n";} //if no driver, no assigning
            else
            {
                int curDriver = q.front(); //take drive in front of queue
                q.pop(); //take the driver id out of queue
                cout << "Assigned driver : " << curDriver << "\n";
            }
        }
    }
}

结果:

Enter command : d
Enter driver's ID : 123
Enter command : d
Enter driver's ID : 124
Enter command : d
Enter driver's ID : 125
Queue is full
Enter command : c
Assigned driver : 123
Enter command : c
Assigned driver : 124
Enter command : c
No driver available
Enter command :

另外，不建议使用 front 之类的关键字。 , remove等...用于变量名称。并查看 Why is "using namespace std;" considered bad practice?