Goals
Implement linear data structures using STL Containers
In this lab, 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 i th 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
You will submit the following files in a zip file to TEACH:
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%
