CS250 Unit 11 Project: Stacks and Queues
Table of Contents
1. Introduction
- About
- Goals
- Debugging
- Setup
- Starter code
- https://gitlab.com/moosadee/courses/-/tree/main/wip_projects/starter_code/c4_u11_StacksQueues?ref_type=heads
- Doxygen documentation
- Queue (Array-based): doxygen/c4_u11_StacksQueues/classDataStructure_1_1ArrayQueue.html
- Queue (Link-based): doxygen/c4_u11_StacksQueues/classDataStructure_1_1LinkedQueue.html
- Stack (Array-based): doxygen/c4_u11_StacksQueues/classDataStructure_1_1ArrayStack.html
- Stack (Link-based): doxygen/c4_u11_StacksQueues/classDataStructure_1_1LinkedStack.html
1.1. Getting started
1.1.1. Creating a new branch
- Check out the main or master branch first:
git checkout main - Get latest changes:
git pull - Create a new branch:
git checkout -b BRANCHNAME
Pull in the starter code from the link above.
2. Implementing the data structure
2.1. Building a structure on top of another structure
The Stack and the Queue structures can each be implemented on top of an Array structure or a Linked structure.
In this case, we have two versions of each: ArrayQueue and LinkedQueue, and ArrayStack and LinkedStack.
You don't have to implement the Push, Pop, and Get functions for queues and stacks from scratch.
For instance, the ArrayQueue and ArrayStack contain SmartDynamicArray<T> m_vector;, and
LinkedQueue and LinkedStack contain LinkedList<T> m_list;.
From within their functionality, you can "pass the buck" to these underlying structures.
| Structure | Push location | Pop location | Get location |
|---|---|---|---|
| Queue | Back | Front | Front |
| Stack | Back (Top) | Back (Top) | Back (Top) |
2.2. Opening the data structure documentation
To access the data structure's auto-generated documentation, go to these pages:
- Queue (Array-based): doxygen/c4_u11_StacksQueues/classDataStructure_1_1ArrayQueue.html
- Queue (Link-based): doxygen/c4_u11_StacksQueues/classDataStructure_1_1LinkedQueue.html
- Stack (Array-based): doxygen/c4_u11_StacksQueues/classDataStructure_1_1ArrayStack.html
- Stack (Link-based): doxygen/c4_u11_StacksQueues/classDataStructure_1_1LinkedStack.html
(All the documentation on the doxygen page is also written out in the data structure's comments.)
You can click on a function name to view the detailed notes about the structure and how to implement it.
2.3. Running the unit tests
There are unit tests already provided for the entire structure. Use these to validate your work. If all your unit tests pass (and the tester doesn't crash before the end then you can assume that your data structure probably works correctly.
3. Updating the program
This program is the same as with the Dynamic Array structure. Replace the vector (or SmartDynanicArray) with
the LinkedList structure and update the function calls.
For example: Implementing ArrayQueue's Push function?
template <typename T> void ArrayQueue<T>::Push( const T& newData ) { throw Exception::NotImplementedException( "ArrayQueue::Push is not implemented" ); // TODO: Erase me once you implement this function! }
ArrayQueue contains SmartDynamicArray<T> m_vector as a member variable. So, pass on the information to the internal data structure:
template <typename T> void ArrayQueue<T>::Push( const T& newData ) { m_vector.PushBack( newData ); // Pass the data on through. }
Each function's Push, Pop, and Get (Top/Front) will be one line of code.