The queue at a restaurant is very busy!! The restaurant needs help reading their data for this queue. The history of the queue’s insertions and removals is in the file formatted like this:
In Turkey sub
Out
In Ham sandwich
In Cookie
In Apple pie
Out
Out
In Turkey sub
“In” is an addition to the queue. All “in” statements have the person’s order directly after “In,” separated by a space. “Out” is a removal in the queue. Orders are listed from the top of the file to the bottom.
In this example, a turkey sub is added then removed. Then, a ham sandwich, cookie, and apple pie is added. The ham sandwich then the cookie is then removed. Finally, a turkey sub is added.
The restaurant needs to know what the next person’s order is after 500 people have been served.
Test Data: