In this lab, using C++, you will create two data structures: a stack and a queue. You will use STL containers to demonstrate basic ADTs.

Queue

For the queue, you will simulate a buffer. Remember it is first-in-first-out. The user will enter a number for the number of rounds to run your simulation. You need one function that randomly generates a number. You will also have a user specified percentage, and the function uses this percentage to randomly put the generated number in the buffer. For example, if the user enters 25, then there is a 25% chance of the randomly generated number been put into the queue. You will have another user specified percentage, which is the chance of a value being removed from the buffer. For example, if the user enters 50, then there is a 50% chance of the number in the buffer been removed in this round. You need to record the length of the queue in each round. After each round of the simulation, calculate and display the average length of the queue. Equation to calculate the average length would be: ALi = (ALi-1 * (i-1) + Li ) / i, where ALi and ALi-1 are the average length in the ith and i-1th round and Li is queue length in the ith round. Does your buffer behave as expected, i.e. get longer if the input chance is greater, and get shorter if the removing chance is greater? Your program needs to handle the situation when the queue is empty and still try to remove a value. You can start the simulation with a queue of certain length.

Stack

Use a stack to create a function that creates a palindrome, i.e. a string that is the same forwards and backwards. It does not need to be an actual word. The function will receive a string from user input and it will return the string with the palindrome. For example, if you enter a string abc, your program will return abccba.

Testing program

Create a menu program for the user to test your buffer and to create a palindrome. For the queue, prompt the user to enter the two chances and the total number of rounds. Display the results to the screen in each round. For the stack, prompt them to enter a string. Create the palindrome and then display it. You can determine how this menu program should look like as long as it test the queue and stack properly.

What to submit Code to implement your stack, both header and source files Code to implement your queue, both header and source files Code to test the operation of your stack and queue. A makefile.

Grading Programming style: 10% Code to implement your stack: 30% Code to implement your queue: 30% Code to demonstrate the operation of your buffer and palindrome creator: 30%