CS250 Unit 11 Project: Stacks and Queues

Table of Contents

1. Introduction

1.1. Getting started

1.1.1. Creating a new branch

  1. Check out the main or master branch first: git checkout main
  2. Get latest changes: git pull
  3. 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:

(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.

Author: Rachel Wil Sha Singh

Created: 2023-10-22 Sun 20:09