/** stack (array) array constructor
* Constructor for stack. Copy items from an array as initial items
* on the stack.
*
* @param initItems An array of items to copy/push onto the stack. The item
* at index 0 of the array will be the bottom of the stack, and the
* last item will end up on the top.
* @param length The total number of items in the array to copy/push onto
* the new stack.
*/
template
AStack::AStack(T initItems[], int length)
{
allocSize = length;
topIndex = 0;
items = new T[allocSize];
// copy the init items to our block of memory. Also
// we update the topIndex to use as our iterator index
// and incidentally it will be correctly set to point to
// the top of the stack once this copy is finished.
for (topIndex = 0; topIndex < length; topIndex++) { items[topIndex] = initItems[topIndex]; } } /** stack (array) destructor */ template
AStack::~AStack()
{
// free up currently allocated memory
delete [] items;
}

/** stack (array) clear
* Function to initialize the stack back to an empty state.
* Postcondition: topIndex = 0; isEmpty() == true
*/
template
void AStack::clear()
{
topIndex = 0;
}

/** stack (array) isEmpty
* Determine whether stack is currently empty or not.
*
* @returns returns true if the stack is empty, otherwis
* returns false.
*/
template
bool AStack::isEmpty() const
{
return topIndex == 0;
}

/** stack (array) push
* Add newItem to the top of the stack.
* Preconditon: The stack exists
* Postcondition: The stack is changed and newItem is added to the top
* of the stack.
* @param newItem The new item to push on top of this stack.
*/
template
void AStack::push(const T& newItem)
{
// if stack is full, grow it
if (topIndex == allocSize)
{
// double the current size
allocSize = 2 * allocSize;
// alloc the new space
T* newItems = new T[allocSize];
// and copy the stack to the new storage space
for (int index = 0; index < topIndex; index++) { newItems[index] = items[index]; } // free up the old space, start using the new space delete [] items; items = newItems; } // add the item, and increment our top items[topIndex] = newItem; topIndex++; } /** stack (array) top * Peek at and return the top element of the stack. * Preconditon: The stack exists and is not empty * Postcondition: If the stack is empty, we throw StackEmpty * exception; otherwise, the top element of the stack is * returned * * @param newItem The new item to push on top of this stack. * * @returns T Returns the top item of type T on the stack. */ template
T AStack::top() const
{
//assert(topIndex != 0);
if (topIndex == 0)
{
throw EmptyStackException(“AStack::top()”);
}
else
{
return items[topIndex – 1];
}
}

/** stack (array) pop
* Remove the top element from the stack. Some ADT combine pop
* and top. We have two separate operations in this ADT.
* Preconditon: The stack exists and is not empty.
* Postcondition: If the stack is empty, we throw StackEmpty
* exception; otherwise the top element of the stack is removed
* from the stack.
*/
template
void AStack::pop()
{
// assert(topIndex != 0);
if (topIndex == 0)
{
throw EmptyStackException(“AStack::pop()”);
}
else
{
topIndex–;
}
}

/** Stack (array) size
* Return the current size (number of items) on this stack.
*
* @returns int Returns the current stack size.
*/
template
int AStack::size() const
{
return topIndex;
}

/** Stack (array) tostring
* Represent this stack as a string.
*
* @returns string Returns the contents of stack as a string.
*/
template
string AStack::tostring() const
{
ostringstream out;
out << "--TopTop--" << endl; for (int index = topIndex- 1; index >= 0; index–)
{
out << items[index] << endl; } out << "--Bottom--" << endl; return out.str(); } /** Stack (array) indexing operator * Access internel elements of stack using indexing operator[]. * This is not a normal stack operation, we use mainly for testing * so that we can compare if two stack are equal at each internal * element of the stack. For this reason, this operator should * probably be private to the Stack class. * * @param index The index of the item onf the stack we want to access * and return, where index 0 represents the bottom of the stack and * index == size-1 is the top. * * @returns T Returns the item at "index" on the stack. */ template
const T& AStack::operator[](int index) const
{
// bounds checking, we will throw our stack exception if fails
if (index < 0 || index >= topIndex)
{
throw InvalidIndexStackException(“AStack::operator[]”);
}
// otherwise we can directly access the asked for item from our items array
else
{
return items[index];
}
}

//————————————————————————-
// LStack (linked list stack) member functions
/** stack (list) constructor
* Default onstructor for linked list version of stack.
*/
template
LStack::LStack()
{
stackTop = NULL;
numItems = 0;
}

/** stack (list) constructor
* Alternate constructor to construct a stack from a given array
* of values. The first item in the array should be the first item
* pushed on stack, and thus ends up on the bottom of the stack.
*
* @param initItems An array of items to be used to initialize this Stack
* with.
* @param length The length or number of items in the initialization array
* we were given.
*/
template
LStack::LStack(T initItems[], int length)
{
// make sure stack starts off empty before we start pushing the asked for
// items onto the stack
stackTop = NULL;
numItems = 0;
// we will reuse the push() functio to simply push all of the items in
// the array onto this stack
for (int idx = 0; idx < length; idx++) { push(initItems[idx]); } } /** stack (list) destructor * Destructor for linked list version of stack. */ template
LStack::~LStack()
{
clear();
}

/** stack (list) clear
*
*/
template
void LStack::clear()
{
Node* temp;
// iterate through Nodes in stack, freeing them up
// as we visit them
while (stackTop != NULL)
{
temp = stackTop;
stackTop = stackTop->link;
// dellocate this Node memory
delete temp;
}
numItems = 0;
}

/** stack (list) isEmpty
* Implement the base classes isEmpty member function to test if this
* stack is currently empty or not.
*
* @returns bool Returns true if the list is empty, false if it is not.
*/
template
bool LStack::isEmpty() const
{
return stackTop == NULL;
}

/** stack (list) push
* Push a new item onto the stack. Implement the base class virtual
* push function.
*
* @param newItem The new item we are to push onto the top of this stack.
*/
template
void LStack::push(const T& newItem)
{
// dynamically allocate space for the new Node to hold
// this newItem
Node* newNode = new Node;
// initialize the node
newNode->item = newItem;
newNode->link = stackTop;
// now make this new node the new top of stack
stackTop = newNode;
numItems++;
}

/** stack (list) top
* Impelmentation of the base class virtual top method. Access and return
* a copy of the top element currently on this stack.
*
* @returns T Returns the top item of type T from the stack.
*/
template
T LStack::top() const
{
//assert(stackTop != NULL)
if (stackTop == NULL)
{
throw EmptyStackException(“LStack::top()”);
}
else
{
return stackTop->item;
}
}

/** stack (list) pop
* Implement the base class virtual method to pop the top item from this
* stack.
*/
template
void LStack::pop()
{
//assert(stackTop != NULL)
if (stackTop == NULL)
{
throw EmptyStackException(“LStack::pop()”);
}
else
{
// keep track of the current top, so we can deallocate
Node* temp;
temp = stackTop;
// pop off the top
stackTop = stackTop->link;
// deallocate the old top now
delete temp;
// update size after removal
numItems–;
}
}

/** Stack (list) size
* Return the current size (number of items) on this stack.
*
* @returns int Returns the current stack size.
*/
template
int LStack::size() const
{
return numItems;
}

/** stack (list) tostring
* Represent this stack as a string.
*
* @returns string Returns the contents of stack as a string.
*/
template
string LStack::tostring() const
{
ostringstream out;
Node* temp = stackTop;
out << "--TopTop--" << endl; while (temp != NULL) { out << temp->item << endl; temp = temp->link;
}
out << "--Bottom--" << endl; return out.str(); } /** Stack (list) indexing operator * Access internel elements of stack using indexing operator[]. * This is not a normal stack operation, we use mainly for testing * so that we can compare if two stack are equal at each internal * element of the stack. For this reason, this operator should * probably be private to the Stack class. * * @param index The index of the item on the stack we want to access * and return, where index 0 represents the bottom of the stack and * index == size-1 is the top. * * @returns T Returns the item at "index" on the stack. */ template
const T& LStack::operator[](int index) const
{
// bounds checking, we will throw our stack exception if fails
if (index < 0 || index >= numItems)
{
throw InvalidIndexStackException(“LStack::operator[]”);
}
// otherwise we will have to search our list for the desired item
// we will search backwards, so the stackTop node is at index
// numItems-1, and we iterate back through the list till we
// arrive at index
else
{
int currentIndex = numItems – 1;
Node* currentNode = stackTop;
while (currentIndex != index)
{
currentIndex–;
currentNode = currentNode->link;
}
return currentNode->item;
}
}

/** @file assg09-stackfun.cpp
* @brief implementation file for function prototypes for
* Assignment 09 using stacks.
*
* @author Jane Programmer
* @note cwid : 123 45 678
* @note class: COSC 2336, Summer 2020
* @note ide : Atom Text Editor 1.46.0 / build package / GNU gcc tools
* @note assg : Assignment 09
* @date June 1, 2020
*
* Assignment 09 using stacks. Use the given Stack ADT to implement a set of
* functions/algorithms. This implementation file is for the functions you are
* to write for this assignment. You should modify this file by adding
* implementations of the 4 functions you are to write. You need to use the
* Stack ADT given to you, and included for you, for the Stack instances for
* your functions. It is incorrect to include STL stacks or other containers
* here to use for this assignment.
*/
#include “Stack.hpp” // only use the Stack ADT given, do not use STL stacks

—
title: ‘Assignment 09: Applications of Stacks’
author: ‘COSC 2336: Data Structures and Algorithms’
date: ‘Fall 2020’
—
# Objectives
– More practice with recursion.
– Practice writing some template functions.
– Use stack ADT to implement given algorithms.
– Practice using Stack class container given as a library in a separate file.
– Look at some common applications of stacks.
# Description
In this assignment, you will be using the `Stack` abstract data type
we developed for this unit and discussed in our lectures, to implement
4 functions that use a stack data type to accomplish their algorithms.
The functions range from relatively simple, straight forward use of
a stack, to a bit more complex. But in all 4 cases, you should only need
to use the abstract stack interface functions `push()`, `pop()`, `top()`,
and `isEmpty()` in order to successfully use our `Stack` type for this
assignment and the function you are asked to write.
**NOTE** You are to use the Stack ADT abstraction give to you for this
assignment. If you are familiar with STL stack containers, you are not to
use them for this assignment. Part of the assignment is to look over and
learn the Stack ADT implementation we give you here based on our textbook
Stack examples.
# Setup
For this assignment you will be given the following files:
| File Name | Description |
|———————–|—————————————————|
| `assg09-tests.cpp` | Unit tests for the member functions |
| | you are to write. |
| `assg09-stackfun.hpp` | Header file where function prototypes for the |
| | functions you write using stacks should go. |
| `assg09-stackfun.cpp` | Implementaiton file, the implementation of the 4 |
| | functions you write for this assignment go here. |
| `Stack.hpp` | Header file defining a Stack ADT for use in |
| | implementing the functions for this assignment. |
| | You will not make any modifications in this file, |
| | you are only going to be using the given Stack. |
| `Stack.cpp` | Implementation file for the Stack ADT |
| | template class. You also do not make any changes |
| | in this file either. |
Set up a multi-file project to compile the `.cpp` source files
and run them as shown for the class. The Makefile you were
given should be usable to create a build project using the Atom editor
as required in this class. You will only be adding code to the
`assg09-stackfun.[hpp|cpp]` file in this assignment. The `Stack.[hpp|cpp]`
file contains a `Stack` container. You are to use this `Stack` ADT for
the 4 functions you are to write for this assignment.

The general approach you should take for this assignment, and all
assignment is:
1. Set up your project with the given starting code. The files
should compile and run, but either no tests will be run, or tests
will run but be failing.
2. For this project, start by uncommenting the first `TEST_CASE` in
the `assg09-tests.cpp` file. These are the unit tests to test the
functionality of your `doParenthesisMatch()` function, the member function
you are to implement.
3. Add the correct function prototype for the `doParenthesisMatch()` member
function in the `assg09-stackfun.hpp` header file.
The prototype consists of the name of the function, its input
parameters and their types, and the return value of the function.
4. Add a stub for your `doParenthesisMatch()` member function to the
`assg09-stackfun.cpp` implementation file. The function should
have the same signature as the prototype you gave in the header
file. Documentation for the function has not been given for you
this time, so add documentation of your function first. This function
is supposed to return a `bool` result, so you should just initially
return `true` so you can get your code to compile.
5. Your code should compile and run now. Make sure after adding the
function prototype and stub your code compiles and runs. However,
your unit tests will be failing initially.
6. Incrementally implement the functionality of your
`doParenthesisMatch()` member function. You should try to add no more than 2
or 3 lines of code, and then make sure your program still compiles
and runs. Start by adding code to get the first failing test to
pass. Then once that test passes, move on to the next failing
tests until you have all tests passing. If you write something
that causes a previously passing test to fail, you should stop and
figure out why, and either fix it so that the original test still
passes, or remove what you did and try a new approach.
7. Once you have the `doParenthesisMatch()` member function
implemented and all unit tests passing, you should then move on to
the other functions in the order suggested. Some functions
use previous ones in this assignment, so do them in the order given
for you in the tasks below.
# Tasks
You should set up your project/code as described in the previous
section. In this section we give some more details on implementing
the member functions for this assignment. You should perform the following
tasks for this assignment:
1. In the first task, we will write a function that will check if
a string of parenthesis is matching. Strings will be given to the
function of the format “(()((())))”, using only opening “(” and
closing “)”. Your function should be named `doParenthesisMatch()`.
It takes a single string as input, and it returns a boolean result
of true if the parenthesis match, and false otherwise.
The algorithm to check for matching parenthesis using a
stack is fairly simple. A pseudo-code description might be
“`
for each charcter c in expression
do
if c is an open paren ‘(‘
push it on stack
if c is a close paren ‘)’:
then
if stack is empty
answer is false, because we can’t match the current ‘)’
else
pop stack, because we just matched an open ‘(‘ with a close ‘)’
endif
done
“`
Your function will be given a C++ string class as input. It is
relatively simple to parse each character of a C++ string. Here
is an example for loop to do this:
“` c++
s = “(())”;
for (size_t index = 0; index < s.length(); index++) { char c = s[index]; // handle char c of the string expression s here } ``` 2. In the next task, we will also write a function that decodes a string expression. Given a sequence consisting of 'I' and 'D' characters, where 'I' denotes increasing and 'D' denotes decreasing, decode the given sequence to construct a "minimum number" without repeated digits. An example of some inputs and outputs will make it clear what is meant by a "minimal number". ``` sequence output IIII -> 12345
DDDD -> 54321
ID -> 132
IDIDII -> 1325467
IIDDIDID -> 125437698
“`
If you are given 4 characters in the input sequence, the result
will be a number with 5 characters, and further only the
digits ‘12345’ would be in the “minimal number” output.
Each ‘I’ and ‘D’ in the input denotes that the next digit
in the output should go up (increase) or go down (decrease)
respectively. As you can see for the input sequence “IDI”
you have to accommodate the sequence, thus the output goes
from 1 to 3 for the initial increase, because in order to
then decrease, and also only use the digits ‘123’, we need
3 for the second digit so the third can decrease to 2.
Take a moment to think how you might write an algorithm to
solve this problem? It may be difficult to think of any
solution involving a simple iterative loop (though a recursive
function is not too difficult).
However, the algorithm is relatively simple if we use a stack.
Here is the pseudo-code:
“`
for each index, character c in input sequence
do
push character index+1 onto stack (given 0 based index in C)
if we have processed all characters or c == ‘I’ (an increase)
then
pop each index from stack and append it to the end of result
endif
done
“`
Your function should be named `decodeIDSequence()`. It will take a
string of input sequence, like “IDI” as input, and it will return a
string type, the resulting minimal number. Notice we will be
constructing a string to return here, so simply start with an empty
string `string result = “”` and append the digits to the end when
you pop them from the stack as described.
3. In the third task, you will write two functions that will be able
to sort a stack. First of all, you should write a simpler
method that, given an already sorted stack as input, and an
item of the same type as the stack type, the item should be inserted
into the correct position on the sorted stack to keep it sorted.
For example, the stacks will be sorted in ascending order, where
the item at the bottom of the stack is the smallest value, and
the item at the top is the largest, like this:
“`
top: 8 7 5 3 1 :bottom
“`
If we call the function to insert a 4 into this sorted stack, the
result should be:
“`
top: 8 7 5 4 3 1
“`
Your function should be called `insertItemOnSortedStack()`. This
function takes an item as its first parameter, and a reference to a
Stack as its second parameter. You should create and use another
temporary stack in your function in order to accomplish the task.
The pseudo-code to accomplish this insertion is relatively simple:
“`
given inputStack
and create temporaryStack for this algorithm
while top of inputStack > item we want to insert
do
pop topItem from inputStack
push topItem onto the temporaryStack
done
at this point, items on inputStack are <= to the item we want to insert so push item onto inputStack now put items back from temporaryStack to original inputStack while temporaryStack is not empty do pop topItem from temporaryStack push topItem onto the inputStack done ``` The tests given for the insert function use an `AStack` (a stack
of integers) for the tests. You can originally create your function
to use a `Stack &` as its second input parameter. It is
important that the stack be a reference parameter here. Also
notice that instead of specifying an `AStack &`, we specify the
abstract base class `Stack &`. This is to demonstrate the power
of using virtual classes and class abstractions. If you specify
the base class, you can pass an `AStack` or an `LStack` or any class
that is derived from the base `Stack` class, as long as that class
implements all of the virtual functions of the abstract Stack
interface. Once you have your function working for `Stack &`,
templatize your function. We practiced creating function templates
in a previous assignment. Here it should be relatively simple, you
simply need to add the
“` c++
template
“`
before the function, and change the `` to `` to templatize.
Once you do this, you function should still work and pass the
tests using an `` type.
4. Once you have your `insertItemOnSortedStack()` template function
working, it is even easier to use this function to create a
`sortStack()` function. We could implement this function again
using a temporary stack, but for this fourth and final function I
want you instead to create a recursive function. A recursive function
in this case is going to work in essentially the same way, but we will
be using the OS/system function call stack implicitly to perform
the algorithm, rather than explicitly creating and using our own
temporary stack.
Create a function called `sortStack()`. This function should
take a `Stack &` (a reference to a Stack of ``
types) as its only parameters. You will later templatize this
function as well, but all of the tests of sortStack() use
stacks of strings, so get it working first for strings, then
try and templatize the function. This is a void function, it
doesn’t return a result, but it implicitly causes the stack
it is given to become sorted.
The function, as the name implies, will take an unsorted stack,
and will sort them in the same order we used previously, e.g.
in ascending order with the smallest item at the bottom of the
stack, and the largest at the top. The pseudo-code to accomplish
this using a recursive algorithm is as follows:
“`
given inputStack as an input parameter
# the base case
if inputStack is empty, do nothing (return)
# the general case
take top item from inputStack and save it in a local variable
call sortStack(inputStack) recursively on this now smaller stack
# on return, the stack should be sorted, so
insertItemOnSortedStack(my item I popped, inputStack)
“`
Once you have it working for type stacks, also templatize
your `sortStack()` function, so that it will actually work to sort
a `Stack` of any type.
# Example Output
Here is the correct output you should get from your program
if you correctly implement all the class functions and successfully
pass all of the unit tests given for this assignment. If you
invoke your function with no command line arguments, only failing
tests are usually shown by default. In the second example, we use the
-s command line option to have the unit test framework show both
successful and failing tests, and thus we get reports of all of the
successfully passing tests as well on the output.

“`
$ ./test
===============================================================================
All tests passed (47 assertions in 4 test cases)

$ ./test -s
——————————————————————————-
test is a Catch v2.7.2 host application.
Run with -? for options
——————————————————————————-
test doParenthesismatch function
——————————————————————————-
assg09-tests.cpp:28
…………………………………………………………………….
assg09-tests.cpp:33: PASSED:
CHECK( doParenthesisMatch(“”) )
with expansion:
true
… output snipped …
===============================================================================
All tests passed (47 assertions in 4 test cases)
“`
# Assignment Submission
A MyLeoOnline submission folder has been created for this assignment.
There is a target named `submit` that will create a tared and gziped
file named `assg02.tar.gz`. You should do a `make submit` when finished
and upload your resulting gzip file to the MyLeoOnline Submission
folder for this assignment.
“`
$ make submit
tar cvfz assg09.tar.gz assg09-tests.cpp assg09-main.cpp
assg09-stackfun.hpp assg09-stackfun.cpp Stack.hpp Stack.cpp
assg09-tests.cpp
assg09-main.cpp
assg09-stackfun.hpp
assg09-stackfun.cpp
Stack.hpp
Stack.cpp
“`
# Requirements and Grading Rubrics
## Program Execution, Output and Functional Requirements
1. Your program must compile, run and produce some sort of output to
be graded. 0 if not satisfied.
1. (25 pts.) `doParenthesisMatch()` is implemented correctly and is
passing all of the tests. Used a stack of from our class `Stack.hpp`
to implement the algorithm.
1. (25 pts.) `decodeIDSequence()` implemented and correct. Used
a stack from our class `Stack.hpp` stack implementation to implement
the asked for algorithm.
1. (25 pts.) `insertItemOnSortedStack()` implemented and working.
The function is correctly templatized. The function takes
a reference to the Stack abstract class as it second parameter.
1. (25 pts.) `sortStack()` implemented as described and working.
The function was implemented using recursion as required.
The function was templatized as asked for. The function
takes a reference to a `Stack` base class as its only parameter.
## Program Style
Your programs must conform to the style and formatting guidelines
given for this class. The following is a list of the guidelines that
are required for the assignment to be submitted this week.
1. Most importantly, make sure you figure out how to set your
indentation settings correctly. All programs must use 2 spaces for
all indentation levels, and all indentation levels must be
correctly indented. Also all tabs must be removed from files, and
only 2 spaces used for indentation.
1. A function header must be present for member functions you define.
You must give a short description of the function, and document
all of the input parameters to the function, as well as the return
value and data type of the function if it returns a value for the
member functions, just like for regular functions. However, setter
and getter methods do not require function headers.
1. You should have a document header for your class. The class header
document should give a description of the class. Also you should
document all private member variables that the class manages in the
class document header.
1. Do not include any statements (such as `system(“pause”)` or
inputting a key from the user to continue) that are meant to keep
the terminal from going away. Do not include any code that is
specific to a single operating system, such as the
`system(“pause”)` which is Microsoft Windows specific.

/** @file Stack.hpp
* @brief header file for Stack class for Assignment 09 using stacks.
*
* @author Derek Harter
* @note cwid : 123 45 678
* @note class: COSC 2336, Summer 2020
* @note ide : Atom Text Editor 1.46.0 / build package / GNU gcc tools
* @note assg : Assignment 09
* @date June 1, 2020
*
* NOTE: Do not edit this file for Assignment 09. You are to use the Stack
* ADT as given for the assignment.
*
* Assignment 09 using stacks. Use the given Stack ADT to implement a set of
* functions/algorithms. This header file contains the declaration of the Stack
* class container that defines the ADT abstraction for Stacks to use for this
* assignment.
*/
#include
using namespace std;
#ifndef _STACK_H_
#define _STACK_H_

//————————————————————————-
/** stack (base class)
* The basic definition of the Stack Abstract Data Type (ADT)
* and stack operations. All declared functions here are
* virtual, they must be implemented by concrete derived
* classes.
*/
template
class Stack
{
public:
/** clear
* Method to clear out or empty any items on stack,
* put stack back to empty state.
* Postcondition: Stack is empty.
*
* @returns void Nothing returned
*/
virtual void clear() = 0;
/** isEmpty
* Function to determine whether the stack is empty. Needed
* because it is undefined to pop from empty stack. This
* function will not change the state of the stack (const).
*
* @returns bool true if stack is empty, false otherwise.
*/
virtual bool isEmpty() const = 0;
/** push
* Add a new item onto top of stack.
*
* @param newItem The item of template type T to push on top of
* the current stack.
*
* @returns void Nothing is returned
*/
virtual void push(const T& newItem) = 0;
/** top
* Return the top item from the stack. Note in this ADT, peeking
* at the top item does not remove the top item. Some ADT combine
* top() and pop() as one operation. It is undefined to try and
* peek at the top item of an empty stack. Derived classes should
* throw an exception if this is attempted.
*
* @returns T Returns the top item from stack.
*/
virtual T top() const = 0;
/** pop
* Remove the item from the top of the stack. It is undefined what
* it means to try and pop from an empty stack. Derived classes should
* throw an exception if pop() from empty is attempted.
*
* @returns void Returns nothing
*/
virtual void pop() = 0;
/** size
* Accessor method to provide the current size of the stack.
*
* @returns int Returns the current stack size as an int.
*/
virtual int size() const = 0;
/** tostring
* Represent stack as a string
*
* @returns string Returns a string representation of the items on
* this stack.
*/
virtual string tostring() const = 0;

// operload operators, mostly to support boolean comparison between
// two stacks for testing
bool operator==(const Stack& rhs) const;
/** operator indexing
* Virtual function for implementation of operator indexing. Subclasses
* must implement this function.
*
* @param index The index into the Stack of the item we want to access.
*
* @returns T& Returns a reference to the indexed item.
*/
virtual const T& operator[](int index) const = 0;
// overload output stream operator for all stacks using tostring()
template
friend ostream& operator<<(ostream& out, const Stack& aStack);
};