Program 1: Circular Array

I'm working on a computer science question and need support to help me learn.

Please read the instructions carefully.

Overview

In this assignment, students will implement a Data Structure in C++ that fulfills the requirements of both the List and Queue Abstract Data Types (ADTs). Students shall achieve this through multiple inheritance.

Student Learning Outcomes

After completing this assignment, students will:

• Understand the inner-workings of a fundamental data structure and implement it using the C++ programming language.
• Explore polymorphism concepts (i.e. CircularArray == Queue; CircularArray == List)
• Develop cleaner code with an understanding of how to include tests in the design process.
• Adhere to the algorithmic complexity requirements of the data structure.
• Gain familiarity with the C++ class inheritance process.

Requirements

The class instructor shall provide students with several files that constitute a project. These include the following:

Note: The versions of the above files will change as the assignment progresses and oversights become apparent. The class instructor will announce on Canvas when a new version of the file is available for students.

Using these files, students shall develop their own, original source code for the CircularArray.h methods. Ultimately, students must deliver a CircularArray that correctly performs the actions specified in the two interface files. For example, every Queue must provide an enqueue operation, so students must develop this code in their own CircularArray file. For full credit, however, the final product must meet the complexity performance requirements we expect from this style of structure. Thus, adding a single item to the array must occur in constant time.

Moreover, simply creating a Circular Array, although thrilling, pales in comparison to the joy of creating one that includes buffer space and automatically expands and contracts to match the data. Therefore, the circular array for this assignment shall also behave like an array-list (or vector) by dynamically adjusting its size in response to the data it stores. Students will implement two data structures for the price of . . . two really. Both aspects of the assignment require significant work and conceptualization.

The files Queue.h and List.h define the exhaustive set of methods students must implement. The file CircularArray.h has a boiler-plate already built with the required functions, so students need only provide their unique code.

The CircularArray must demonstrate O(1) behavior for addFirst and addLast. Achieving O(1) behavior for add with a standard array is trivial, but removing the first element is impossible in under O(n). A circular array, however, makes removing from the front fast and efficient.

The CircularArray must include a buffer like Vectors and ArrayLists do, and grow dynamically in response to adding and removing items. Thus, some specific insertions and removals from the CircularArray will take longer than O(1), for the data structure occasionally resizes, but the expected value is that the time will remain constant. Students may not use the standard library vector for this purpose and must implement their own version. It is annoying, but a necessary part of the education.

Delivery

On or before the due date, students shall submit their version of CircularArray.cpp and the output their program produced when they ran it locally. The instructors and graders do not require any of the instructor provided files that the students were instructed not to modify. The instructor will use the original versions of these files to make certain no modifications took place.

Grading

Grading is a Scam (and Motivation is a Myth) | A Professor Explains – YouTube (Links to an external site.)

Woops. I accidentally included that link. Please ignore it.

You earn points on this assignment through the following ways:

Other Notes

In this assignment, students may not use external libraries or data structures. In reality, you absolutely would, and there would be no reason to do it the way we are doing it here. That said, we ARE here, so doing it the hard way is a must. It's not about having a working CircularArray from you because I need it to save the planet from being hit by a giant meteor — I have Bruce Willis for that. I will never actually use these CircularArrays for anything. Even the great ones! We do it this way here because it allows us to talk about and use some common programming techniques that will apply in the real world. Also, if you were annoyed because I said meteor and you know full well it was an asteroid, I am unspeakably proud.

Modifying the instructor-only files opens a path to danger. Frequently, students make a *tiny* change and forget about it, and this small change ends up preventing the program from compiling when used with the original files on my computer. In my experience, modifying the instructor files leads to frustration, and frustration turns to anger, anger turns to hate, and hate leads to Star Wars references. Unfortunately, although entertaining, these are not yet usable as currency. Somehow, you knew this . . . somehow, you always knew. Hopefully, however, I've made the request in such an overwhelmingly ridiculous way that you will hear it. Work on CircularArray.h, leave the other files alone, and NO disintegrations!

Before starting work, make certain you understand the requirements. I promise, it will save you time. Use the synchronous class time to clarify everything you need. I will happily answer a question someone already asked, so ask away.

Try to write as many methods in terms of other methods as possible here. There is no reason to have add(index), addFront(), and addLast() all modify the list. Instead, have addFront and addLast CALL add(0) or add(size()). This substantially simplifies the testing you need to perform. If you know add(index) works, and you use that for addFront and addLast, then you don't really need to thoroughly test the latter two methods.

Circular Arrays: Circular buffer – Wikipedia (Links to an external site.)

Array List/ Vector: Dynamic array – Wikipedia (Links to an external site.)

For additional, optional, insight into virtual destructors:Virtual Destructors in C++ – YouTube (Links to an external site.)

If you have the prerequisites, then I don't expect you to understand most of Cherno's video the first time through. It is, however, a great lead in to a helpful channel for learning to code in C++.