Queues are widely used throughout computing to provide a simple first-in / first-out means of organizing data. While it is trivially easy to build a queue with a fixed maximum size, such a queue is of limited utility. Either the queue's maximum size would be too small to make it generally applicable or the queue itself would end up eating far to many system resources.
For this assignment, you will be creating a simple expanding queue class, capable of growing dynamically to hold any number of values provided by the user.
Your program will implement a simple, expandable queue, capable of storing a set of integers. A user will be able to issue simple commands which will cause a value to be added to the queue, a value to be retrieved from the queue, or the queue to be emptied. There is also a command to exit your program.
Your goal is to receive these commands and execute them on your queue. At no time should your program limit the number of values the user can store.
Your program will receive a sequence of commands from cin, with the individual commands separated by whitespace. Here are the commands:
| Command | Meaning |
| i int | Insert the number int at the beginning of the queue. (That is, enqueue it.) |
| e | Empty the queue (remove all numbers within it) |
| r | Retrieve the value from the end of the queue, if possible. (That is, Dequeue the next value.) See Output, below, for details. |
| q | Quit the program. No other output should be generated. |
Example input:
i 10 i 13 i 10 r e r q
Output should only be generated if/when you program received the command r. In that case, you should either print out the 'next' value in your queue, (if the queue is non-empty), or print "empty" if there is nothing currently stored in the queue.
Here are examples illustrating both cases (assume the queue was empty when the first command was received):
| Input |
i 10 i 13 i 10 e r |
Output |
empty |
| Input |
i 10 i 5 i 2 i 1 i 11 r r r |
Output |
10 5 2 |
Your code must include a class which implements the expandable functionality. This class must, at the very least, implement methods for inserting individual values, emptying the queue, and retrieving a value from the queue. You will also need at least one constructor, and you must provide a destructor. Beyond those requirements, the details of the implementation are completely up to you.
You are free to use an array, a linked list, or any other storage facility you wish to hold onto inserted values.
Remember that any memory you allocate with new you must free with delete, and you will have to do dynamic memory allocation.
You will provide a Makefile that I can use to compile and run your program. It needs to include rules for default (just compile the program), clean (delete .o files and the executable), and run (compile, if necessary, and run). The Makefile provided with the solution to Program 1 does everything yours needs to do, so go ahead and modify that to fit your needs.
The main function must be implemented in one file (as was the case with HW1), the binary tree class must be defined separately, and should make use of separate header and implementation files. Other functions / classes (if needed) may be implemented in one or more source files. All source files (except the file with "main") must have their own header file. (The names of the files are not important since you will be providing a Makefile.)
Have fun, and remember that all the usual rules regarding cheating and cooperation are in full effect for this program.
This page last updated 28 May 2010