IV: Data Structures

This worksheet will assess your knowledge of the data structures we have been exploring in the workshop content. The worksheet is formed of two parts; a quiz designed to test your understanding of the topic, and a programming task, designed to test how well you can apply the knowledge in practice.

To complete this worksheet:

Complete the worksheet quiz on learning space
Implement the code for the worksheet task

Submission Instructions

For the final submission, you should submit your completed program.cs file and a PDF of your highest mark in the correct folder in your git repository.

The following filenames are expected:

quiz.pdf - the saved quiz result
Program.cs - your solution to part B

The final repository must not contain the whole CS project/solution. Only the ‘Program.cs’ should be submitted. Your code must also not import any 3rd party libraries, however use of the standard library is fine.

Part A: Quiz

Complete the quiz, ‘Worksheet 4: Data Structures’ on learning space.

Part B: Programming Activity

Examine the provided skeleton project. This is a program designed to implement some of the concepts we have talked about in session, but there are some features missing. Your task is to implement these in such a way that the contract specified in this document, and the comments is met.

You must not alter the function signatures (names, return values, argument types). Doing so will negatively impact your mark, and may result in a mark of zero for this part

You may use any data structure we have spoken about (eg, List, Set, Array) to implement your solution, but you must not use the in-built stack class, or any varients of it. You should also only use functionality present in the standard library. Although the use of collections (List, Set, Dictionarty, etc…) is permitted, the solution quality marks may include the technical complexity of the methods implemented (ie, using arrays vs more complex data structures may be rewarded in this critera).

Core Tasks

The following tasks must be attempted in order to achive adequate or better on the ‘programming activity’ portion of the worksheet. Your methods must not ask for user input during execution, and must not write to standard error or standard out (ie, you don’t need to use Console or similar).

Test data will be provided to these functions via a suitable unit testing framework. If the tests cannot run successfully, or time out (take too long) during execution this will be counted as failing that test. Any attempt to bypass or comprimise the execution envrionment will be treated as academic misconduct.

Stack

A stack is a data structure we have spoken about previously. For this task you must implement one.

The stack will be provided with an initial capacity, this should be the initial capacity of the queue (ie, how many elements it can store).

Your stack must implement the following methods, the stack must be able to handle storing upto capacity elements:
- A push method, which takes an item to add to the stack
- A pop method, which removes the top item from the stack and returns it
- The pop method must return -1 if the stack is empty
- isEmpty must return true if the stack contains no elements, else it should return false
- getSize must return the number of elements contained in the stack
- Peek must return the top element of the stack, but not remove it. If such an element does not exist, it should return -1
Your stack should be able to handle more elements than the initial capacity (ie, allows arbitary adding and removal)

Queues

A queue is an abstract data type we have discussed earlier in this module.

The queue will be provided with an initial capacity, this should be the initial capacity of the queue (ie, how many elements it can store).

Your stack must implement the following methods, the queue must be able to handle storing upto capacity elements:
- The front method must return the front of the queue, or -1 if the queue is empty
- The enqueue method must place an element at the end of the queue
- The dequeue method must remove the front element from the queue, and return it, or -1 if no such element exists
- isEmpty must return true if the stack contains no elements, else it must return false
- GetSize must return the current number of elements in the queue, or 0 if the queue is empty
Your queue should be able to handle more elements than the initial capacity (ie, allows arbitary adding and removal)

Advanced Tasks

These are advanced tasks intended to provide a challenge or extend your knoweldge (including providing an opportunity to explore refactoring). It is advised to attempt all of the core tasks first.

For each of these activities, there are required (must) and extention (should) tasks. As with the core tasks, no marks will be awarded for extention tasks unless the core requirements are met.

Stack-based Calculator (ints)

For this task, you wll be expected to implement a simple stack-based calculator. You will be provided with a series of inputs, in the form of an array. This consitute a set of mathmatical operators expressed in postfix notation.

You are advised to refer back to our initial programming tasks for parsing inputs.

For example, the following expression:

5 6 +

Means:

Add 5 to the stack
Add 6 to the stack
Pop the top two values from the stack, add them together then push the result onto the stack.
your implementation must be able to handle whole numbers from 0 - 255
your implementation must handle four basic mathmatical operators:
- + means addition
- - means subtraction
- * means multiplication
- / means division
your function should return -1 in the event on an error (eg, not enouph arguments on the stack)
your function should be robust against invalid inputs

Stack-based calculator (floats)

You should implement a float-based version of the RPN calculator (RPNFloat):

It must must the requirements listed above
you must handle both floating point numbers as inputs and arbitary-sized integers (ie, 1000 -> 1000.0) as well as the following additional inputs
- ‘%’ means remainder (modulo)
- ‘sin’ which means (sine)
- ** which means ‘power of’
your function should return -1.0F in the event on an error (eg, not enouph arguments on the stack)
your function should be robust against invalid inputs

Rubric

Section	Task	Must	Should	Subtotal
Quiz		/₂₀	/₁₀	/₃₀
Core Tasks	Stack implementation	/₁₀	/₇	/₃₀
Core Tasks	Queue implementation	/₈	/₅	/₃₀
Advanced Tasks	RPN calculator (ints)	/₁₀	/₅	/₂₄
Advanced Tasks	RPN calculator (floats)	/₄	/₅	/₂₄
Solution Quality	-	-	/₁₆	/₁₆
		/₅₂	/₄₈	/₁₀₀