Due: October 22th, 2023 11:59 PM
Topics: Templates, Linked Lists, Stacks, Queues
⚠️ DO NOT change files marked with// DO NOT CHANGE THIS FILE
In this homework, you will write a template library that contains three data
structures - LinkedList
, Stack
, and Queue
.
You will implement LinkedList
first and then implement Stack
and Queue
using the LinkedList
you implemented.
In reality,
Stack
andQueue
can also be implemented using a dynamically-sized array (such asstd::vector
), but not in this homework.
You will all be graded only on the same (hidden) test cases your TAs created.
We provided some test cases in ./tests. Feel free to modify and add more test cases, but the ./tests in your submission will not be graded. However, you will be able to see the results of your submitted test cases on Gradescope.
LinkedList
Implementation - 60%Stack
Implementation - 15%Queue
Implementation - 15%- Memory Safety - 10%
NOTE: If you are running out of time to implement all methods, please at least provide a syntactically valid empty method definition for each method in
lib/*.cpp
to make autograders' test cases compile.
-
Check the definition for
LinkedListNode
in lib/LinkedListNode.hpp. -
Check the spec in lib/LinkedList.hpp and implement all methods in lib/LinkedList.cpp.
-
Create test cases in tests/LinkedListTest.cpp.
-
Check the spec in lib/Stack.hpp and implement all methods in lib/Stack.cpp.
-
Create test cases in tests/StackTest.cpp.
-
Check the spec in lib/Queue.hpp and implement all methods in lib/Queue.cpp.
-
Create test cases in tests/QueueTest.cpp.
We will run valgrind --leak-check=full ./build/run_tests
against the hidden
test cases to check whether there is any memory safety issue.
If your test cases are not comprehensive, valgrind
may not be able to report
potential memory safety issues when you run against your test cases.
If you do not fully implement the data structures, your score for memory safety
will be automatically discounted even if valgrind
does not report error(s).
(For example, if you implement nothing, there will of course be no memory safety issues, but you will receive a 0 on memory safety score).
Use ./generate_submission.sh
and submit hw1-submission.zip
on Gradescope.
Use one of the following options to set up your environment.
⚠️ If you're a student, DO NOT FORK this repository because you cannot change the visibility of a forked repo to private. If you plan to use Git for version control (which is encouraged), runrm -rf .git && git init
after setting up using one of the options below and push to your private repository. Any public repository containing part of this homework solution will be reported to SJA.
-
If Docker is not running, start Docker.
-
Click the following button to set up the environment.
-
When asked for selecting a Kit to configure CMake, choose GCC.
-
Connect VS Code to the remote host.
-
Install C/C++ Extension Pack on Remote Server (if not already).
-
Run the following command inside the integrated terminal.
git clone https://github.com/ecs36c-fq2023/hw1 ecs36c-hw1
-
Run
code ./ecs36c-hw1
to open the folder. -
When prompted to configure CMake, confirm and choose GCC when prompted for kit selection.
-
Run the following commands
git clone https://github.com/ecs36c-fq2023/hw1 ecs36c-hw1 cd ./ecs36c-hw1 mkdir build cd build cmake ..
Directly Launch.
cd build
make
./run_tests