Please help me solve this data structure problem using C++ Please write comments
ID: 3699624 • Letter: P
Question
Please help me solve this data structure problem using C++
Please write comments in the code
Please also write a short description about how the program works. Thank you
_______________________________________________________________________________
Please use stack and queue to simulate the situation:
National Cheng Kung university buy a bus, from Tainan train station to National
Cheng Kung University. The bus can accumulate 4 people (total weight: 260kg),
with only one door. The order of getting in/out bus is FIFO(first in first out).
And there is a bus stop at Tainan train station, which can only
accumulate 8 students for waiting.
When bus arrive, the first four students gets in the bus in order.
If the students overweight the weights that the bus can afford,
the last student getting in the bus should get out the bus.
And the next student can get in the bus. When the bus is gone,
the following students can get in the waiting line at the bus stop.
(Remember the upper bound of the amount of waiting students is 8)
There are 20 students want to get in the bus stop in order.
Their weights are {70,67,75,55,51,40,87,65,58,86,66,43,57,76,68,61,60,63,39,74}
Question: What is the order of the students arrived National Cheng Kung university?
(Please show the sequence of the weights of the students)
Requirement:
a. Please use Queue to stimulate the bus stop, and use Stack to stimulate the bus.
b. Print out the situation of getting in/out the bus and the situation of getting in/out the bus stop every time.
(The student who is overweight should get in the bus and then back to the weighting line.)
Hint: Use a for loop to check. If there are less than 20 students arriving National Cheng Kung university, then keep going.
Explanation / Answer
So the basic working of the program is as follows:
1) Most outwards while loop is there to check the condition if all the people have made it to the destination, using people_destination
2)The first inner while loop is to keep adding people to the station in case they are less than 8
3)This second inner loop has dual functionality, it is to board people onto the bus while keeping the weight below 260, and also side by side keeps adding to the station(queue) as the people board the bus(stack).
4)The condition whether people_destination = 20 is used to break out of the infinte loop
5) Rest all is pretty basic C++ STL
6) Also the one thing i have assumed is that, the person which has to deboard the bus in case of overweight situation, goes to the end of the queue at the station and doesn't stay at the front.
7)The code for keeping him at the front is pretty straightforward too incase you need it
#include <iostream>
#include <queue>
#include <stack>
using namespace std;
int main()
{
queue<int> q; // initializing a queue
stack<int> s; // initializing a stack
int people_queue = 0;
int people_bus = 0;
int people = 20;
int arr[] = {70, 67, 75, 85, 51, 40, 87, 65, 58, 86, 66, 43, 57, 76, 68, 61, 60, 63, 39, 74};
int count_station = 0; // to count the amount of peoople that have reached the station
int weight;
int count_destination = 0; // to count the amount of people that have the destination
while (1) // making an infinite loop with break condition
{
while (people_queue < 8 && count_station < 20) // loop to keep people entering the station in the queue
{
q.push(arr[count_station]);
people_queue++;
cout << arr[count_station++] << " entered the station." << endl;
}
weight = 0;
while (people_bus != 4 && q.empty() == 0 && weight <= 280) // loop to make people board the bus, *IMP* less than 4 people can also board the bus if the weight condition is satisfied
{
weight += q.front(); // calcualting the weight of people on board
if (weight <= 280) //checking if its below 280
{
s.push(q.front());
q.pop();
if (count_station < 20) // condition is necessary to ensure that the station doesn't try to access people out of bounds
q.push(arr[count_station]);
people_bus++;
cout << arr[count_destination++] << " entered the bus." << endl;
if (count_station < 20) //
cout << arr[count_station++] << " entered the queue." << endl;
}
else // I am assuming the guy that has to get off goes to the end of the queue
{
int c = q.front(); // getting the weight of the guy in front
q.pop(); // making the second person to be at the front
q.push(c); // pushing the person at the start to the end
cout << c << " had to deboard the bus and went to the end of the queue" << endl;
weight -= c;
}
}
if (people_bus == 4)
{
for (int i = 1; i <= people_bus; i++) // loop to remove all the people from the bus
{
int c;
c = s.top();
cout << c << " got off the bus at the destination." << endl;
s.pop();
}
people_bus = 0;
}
if (count_destination == 20) // to check if all the people recahed the destination and to break out of the infinite loop
{
cout << "Everyone has reached their destination." << endl;
break;
}
}
}