C++ Programming (02)

Follow the instructions and do the programming.

Topics Covered:

  • The sorted array-based list
  • The array-based stack
  • The array-based queue

Goals:

  • To add an algorithms to the array-based list that maintains a sorted order when inserting and deleting.
  • To understand the the stack and queue and their characteristics.
  • To understand the use of a circular array and it’s application to the implementation of a queue.

——————————————–PROJECT START HERE———————————————————————————————————–

Using the UML and class descriptions below, implement your choice of either a stack data structure, or a queue data structure. You are not required to do both.

Neither class contains any cin or cout statements. They do not directly interact with the user in any way.

All accessors should be marked const.

Your header files should include standard C++ preprocessor guards (#ifndef, #define, #endif).

Class Descriptions:

MyStack:

Class Variables:

  • list – a pointer that holds the memory address for an array of integers.
  • top – an integer that stores the index of the array element storing the top value of the stack. A value of -1 means the stack is empty, and a value of max – 1 means the stack is full.
  • max – the number of elements in the array whose address is stored in list.

Class Methods:

  • Constructor – accepts an integer as it’s only argument. Initializes max with the argument and then dynamically allocates a new array of max elements, storing it’s address in list. Initializes top to -1.
  • Destructor – frees all memory used by the MyStack object.
  • push – pushes it’s argument onto the stack. Returns 0 if successful, -1 otherwise. The push operation will fail if the stack is full.
  • pop – removes the top value from the stack. Returns 0 if successful, -1 otherwise. Fails if the stack is empty.
  • peek – assigns the top value of the stack to it’s reference parameter if the stack is not empty. Assigns nothing to the reference parameter if the stack is empty. Returns 0 if the stack isn’t empty, -1 otherwise.

MyQueue:

Class Variables:

  • list – a pointer that holds the memory address for an array of integers.
  • front – an integer that holds the index of the element that stores the first value in the queue.
  • back – an integer that holds the index of the first element after the element that stores the last value in the queue.
  • max – the number of elements in the array whose address is stored in list.

Class Methods:

  • Constructor – accepts an integer as it’s only argument. Initializes max to the argument. Dynamically allocates an integer array of max elements, storing the address in list. Initializes front and back to 0.
  • Destructor – frees all memory used by the MyQueue object.
  • enqueue – Accepts an integer as it’s only argument. Adds the argument to the back of the queue. Returns 0 if successful, -1 otherwise. Fails if the queue was full.
  • dequeue – Removes the value at the front of the queue. Returns 0 if successful, -1 otherwise. Fails if the queue was empty.
  • first – assigns the value at the front of the queue to it’s reference parameter. Returns 0 if successful, -1 otherwise. Fails if the queue was empty. Assigns nothing to the reference parameter if the queue is empty.

Hints:

  • You are responsible for all data structures covered in this unit on the exam.
  • Even though you are only required to submit an implementation of one of the data structures above, do both and submit the one you feel most confident about.
  • Test your implementation by adding to and removing values from the data structure. Use peek or first to check the values are being removed in the correct order.
  • No exception handling is required in this assignment.
  • Here’s a driver you can use to get you started on your testing: hw-02-driver.cppView in a new window. It is not complete and not a guarantee of a perfect score.

Submission Details:

Submit either your queue implementation in a file named MyQueue.h, or your stack implementation in a file named MyStack.h. Do not submit both.

"Order a similar paper and get 100% plagiarism free, professional written paper now!"

Order Now