实现与链表堆栈的交集

Question

嗨，我有一项家庭作业，需要在两个小时内实现两条单行道的交叉口。我需要调整阶段，使每个队列的车辆数量理想地少于5辆，9辆也是可以接受的。

这一切都起作用，只是我的分阶段实施方式出现了问题，我似乎无法理解这个问题。我能得到的最好的结果是一个队列是0或1，另一个是40+。我似乎不能让他们两个都在9岁以下。我已经把问题归结为我的阶段检查，但想不出解决问题的方法。我知道我想稍微支持Q1，因为汽车到达Q1的速度比Q2稍快。

提前感谢您的帮助。

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
using namespace std;
struct Node {
    int data;
    Node *next;
};
class Queue {
private:                         
    Node *listpointer;
public:                          
    Queue();
    ~Queue();
    void push(int newthing);
    void pop();
    int top();
    bool isEmpty();
    int queueCount();
    void Queue::popTwo();
    bool Queue::twoOrMore();
};
Queue::Queue() {
//constructor
    listpointer = NULL;
}
Queue::~Queue() {
//destructor
}
void Queue::push(int newthing) {
//place the new thing on top of the Queue
    Node *temp;
    temp = new Node;             
    temp->data = newthing;
    temp->next = listpointer;
    listpointer = temp;
}
void Queue::pop() {
//remove top item from the Queue
    Node *p;
    p = listpointer;
    if (listpointer != NULL) {
        listpointer = listpointer->next;
        delete p;  
  }
}
int Queue::top() {
//return the value of the top item
    return listpointer->data;
}
bool Queue::isEmpty() {
//returns true if the Queue is empty
    if (listpointer == NULL) {
        return true;
    }
    return false;
}
int Queue::queueCount() {
    Node *temp;
    int count = 0;
    temp = listpointer;
    while (temp != NULL) {
        ++count;
        temp = temp->next;
    }
    return count;
    delete temp;
}
void Queue::popTwo() {
// remove the 2 top items from the stack
    Node *p;
    p = listpointer;
    if (listpointer != NULL) {
        listpointer = listpointer->next;
        delete p;
    }
    p = listpointer;
    if (listpointer != NULL) {
        listpointer = listpointer->next;
        delete p;                
    }
}
bool Queue::twoOrMore() {
// return true if the stack has at least two items
    if(listpointer==NULL || listpointer->next==NULL) return false;
    else return true;
}
//implement/copy your queue structure and functions above
//then, declare two instances:
//Queue Q1, Q2;
//if you want, make a separate function to change the 
//signals between the queues (either green or red)
//When the signal changes, one queue only is allowed to delete elements
Queue Q1, Q2;
int Q1phase = 30; //initial attempt
int Q2phase = 60; //initial attempt
const int Q1arrive = 18; //fixed 
const int Q2arrive = 22; //fixed
const int leave_rate = 10; //fixed, one car leaves either queue every 10 seconds
int car_id=0;
int clock=0;
bool Q1_green, Q2_green; //indicates which queue is opened, only one at a time
int main(int argc, char **argv) {
    //if(argc!=3) {printf("needs: Q1phase Q2phasen"); exit(0); }
    //Q1phase=atoi(argv[1]);
    //Q2phase=atoi(argv[2]);
    if(Q1phase < 30 || Q2phase < 30) {printf("Minimum time for each queue to be closed is 30 secondsn"); exit(0);}
    clock = 0;
    car_id = 0;
    Q1_green = true;
    Q2_green = false;
    int length_Q1, length_Q2;
    length_Q1 = 0;
    length_Q2 = 0;
    while (clock < 7200) {
        clock++;
        if (clock % Q1arrive == 0) {
            car_id++;
            //car_id join Q1
            Q1.push(car_id);
            length_Q1 = Q1.queueCount();
        }
        if (clock % Q2arrive == 0) {
            car_id++;
            //or car_id join Q2
            Q2.push(car_id);
            length_Q2 = Q2.queueCount();
        }
        if ((clock % Q1phase == 0) || (clock % Q2phase == 0)) {
            if (Q1_green == true) {
                Q1_green = false;
                Q2_green = true;
            } else {
                Q1_green = true;
                Q2_green = false;
            }
        }
        if (clock % leave_rate == 0) {
            if (Q1_green == true) {
                Q1.pop();
                length_Q1 = Q1.queueCount();
            }
            if (Q2_green == true) {
                Q2.pop();
                length_Q2 = Q2.queueCount();
            }
        }
    //ChangeSignal();//every second, check if it is time to change signals (phasing is important!)
    //After the signal change:
    //verify which queue is opened
    //either Q1 or Q2 will have the chance to delete one element (Q.Leave())
    //
    printf("at time %d:nthe current length of Q1 is %dn",clock,length_Q1);
    printf("the current length of Q2 is %dn", length_Q2);
    //at the end of the simulation, both queues should have few cars
  }
}

Answer 1

您的总到达率超过了离开率，因此汽车将不得不积压。

总到达速率为1/22 + 1/18 =~ 0.1010辆/秒。这超过了每秒0.1辆车的离开率

光每30秒变化一次（Q1phase），因为Q2phase是Q1phase的倍数。所以基本上队列有一个相等的工作循环。

车辆从每个队列中排出的速度是总速度的一半：一个队列0.05，另一个队列0.05%（1/20）。

请注意，1/20的休假率小于1/18。因此，到达时间为1/18的队列将积压。1/20的离开率大于1/22，因此到达率为1/22的队列不会积压。

这种细微的差别并不是很小！超过休假率和不超过休假率之间存在着天壤之别。

---

哦，下面是如何计算积压队列中的汽车：

到达率：1/18。休假率：1/20（1/10的一半）总时间：7200秒：

7200*（1/18）-7200*（1/20）==？？？？

：）