03_Queue_Lab
Implement an array-based queue in C++
Note: When you create your project, do NOT add ArrayQueue.ipp to the list of source files, add it to the list of include files. You will see that ArrayQueue.ipp is #included at the bottom of ArrayQueue.h. See ArrayQueue.h for more explanation.
Requirements
- remove takes O(1) time
- add takes O(1) time, unless it calls grow (in that case O(n) is okay)
- grow is only called if the number of items == backingArraySize, and the size of the array is doubled during grow
- grow takes O(n) time
- Do not leak memory (make sure grow and the destructor do the right thing)
- getNumItems is O(1) time
- add and remove throw excpetions as appropriate
- You must use the array in a circular fashion. If you don't do this you probably won't be able to get #1, #2 and #3 to all be true.
Reading
"Open Data Structures," Chapter 2, up through section 2.4 (ArrayDequeue). http://opendatastructures.org/ods-cpp/2_Array_Based_Lists.html
Information about the Von Neumann computing model may be helpful. This optional reading is section 2.2 of "Algorithms and Data Structures: A Basic Toolbox" by Melhorn and Sanders. A free copy may be found here: http://www.mpi-inf.mpg.de/~mehlhorn/ftp/Toolbox/Introduction.pdf
Questions
1. Which of the above requirements work, and which do not? For each requirement, write a brief response.
- TODO
- TODO
- TODO
- TODO
- TODO
- TODO
- TODO
- TODO