$10$:$25m$

$69$

Back Project $1$ Handout

CS $251-$ Data Structures & Algorithms

Spring $2024$

Project $1$: Stacks and Queues

Due: $01/31/2024$ at $11$:$59$PM

General Guidelines:

The APIs given below describe the required methods in each class that will be tested. You may need additional methods or classes that will not be directly tested but may be necessary to complete the assignment. Keep in mind that anything that does not need to be public should generally be kept private $($instance variables, helper methods, etc.$).$ Additional file creation isn't allowed as Vocareum will only compile the files given in the startercode.

In general, you are not allowed to import any additional classes or libraries in your code without explicit permission from the instructor! Adding any additional imports will result in a $0$ for the entire project.

Note on Academic Dishonesty:

Please note that it is considered academic dishonesty to read anyone else's solution code to this problem, whether it is another student's code, code from a textbook, or something you found online. You MUST do your own work! You are allowed to use resources to help you, but those resources should not be code, so be careful what you look up online.

Note on implementation details:

Note that even if your solution passes all test cases, if a visual inspection of your code shows that you did not follow the guidelines in the project, you will receive a $0.$

Note on grading and provided tests:

The provided tests are to help you as you implement the project. The Vocareum tests will be similar but not exactly the same. Keep in mind that the points you see when you run the local tests are only an indicator of how you are doing. The final grade will be determined by your results on Vocareum.

CS $251-$ Data Structures & Algorithms

Spring $2024$

Project Overview:

In this project, you will work on two problems. First, we will implement a Double Ended Cyclic queue, and then we will use that queue to find a solution to a maze or generate a maze with a given seed.

Part $1$: Double Ended Cyclic Queue $(40$ Points$)$:

In part $1,$ you must implement a Double Ended Cyclic Queue. Adding an element is called enqueue and removing an element is called dequene In a traditional queue elementsare always enqueued at the tail

$10$:$25m$

$69$

Back

Project $1$ Handout

CS $251-$ Data Structures & Algorithms

Spring $2024$

Project Overview:

In this project, you will work on two problems. First, we will implement a Double Ended Cyclic queue, and then we will use that queue to find a solution to a maze or generate a maze with a given seed.

Part $1$: Double Ended Cyclic Queue $(40$ Points$)$:

In part $1,$ you must implement a Double Ended Cyclic Queue. Adding an element is called enqueue and removing an element is called dequeue. In a traditional queue, elements are always enqueued at the tail of the list and dequeued from the head. However, in this version, we allow enqueue and dequeue at both the front and the back of the queue. We will implement a cyclic queue to utilize memory better. The underlying data structure that we will use is a dynamically resizable circular array.

Main idea:

Memory in computers is not circular, however, we can make it behave like a ring. The idea is to circle back when the end of the memory is reached. Another important factor is that Arrays have a fixed size; Queues do not. Therefore, we must occasionally resize the array. The guideline for resizing the array is as follows:

When the array becomes full, initialize a new array with

length $=($ old length $)**$ increaseFactor

Copy the elements over from the old array to the new array. When copying, reorganize the array such that the front element is back at index $0$ in the new array. I.e$.,$ the array is linear after resizing.

Note: only resize when an enqueue would cause an overflow. If an enqueue causes the array to become full, do not prematurely resize. Wait until the next enqueue, and resize before inserting the new element.

$2.$ If the capacity of the array is larger than $4$ times the size of the array, reduce the size of the array by the decreaseFactor.

length $=(old$ length$)\frac{?}{?}$ decreaseFactor

However, the size should not be shrunk further than the initial capacity. Say for example, the initial capacity is $7,$ the array size should never be reduced below $7.$

Note: you should shrink the array directly after a dequeue or pop that causes the above situation. Do not wait until the next dequeue $/$ pop.

You are encouraged to have a look at the API below and the starter code before reading the handout further. Please also have a look at the documentation comments in the starter code.

CS $251-$ Data Structures & Algorithms

Spring $2024$

Class: cylic$\_$double$\_$queue:

$10$:$25m$

$69$

Back

Project $1$ Handout

However, the size should not be shrunk further than the initial capacity. Say for example, the initial capacity is $7,$ the ar