Purpose This assignment is an exercise in implementing the stack ADT using a sin

Question

Purpose

This assignment is an exercise in implementing the stack ADT using a singly-linked list. This assignment also introduces the concept of templates.
Assignment

This program creates and implements a class to represent the Stack ADT using a singly-linked list.

A driver program is provided for this assignment to test your implementation. You don't have to write the tests.
Program

You will need to write one template structure and one template class for this assignment, called SNode and Stack. You will need to implement several methods and functions associated with these data types.

Since these are both C++ templates and are closely related to each other, all of your code should be placed in a single header (.h) file. This includes the implementations of all methods and any other associated functions.
struct SNode

Data members

This template structure should have two data members: a member of the template parameter type to store an item to be inserted into the stack, and a pointer to an SNode. The pointer next will point to the next node in the linked list (or be NULL if this is the last node in the list).

Since the Stack class will need access to these data members, make them public (the default for a struct).

Methods

*

Constructor

The structure should have one constructor that takes an argument of the template parameter type. Make this argument a reference to const data. The constructor should copy the argument into the stack node and set the node's pointer to NULL.

class Stack

Data members

This class should have one data member, a pointer to an SNode. The pointer sTop will point to the front node in the stack (or be NULL if the stack is empty).

Methods and associated functions

*

Constructor

The class should have a default constructor that takes no arguments. The constructor should set sTop to NULL.
*

Destructor

The class should have a destructor. The destructor can simply call the clear() method described below.
*

Copy constructor

The class should also have a proper copy constructor.
*

operator=

The assignment operator should be properly overloaded.
*

operator<<

The output operator should be overloaded so that an entire Stack can be sent to the standard output. As usual, this function will need to be a friend rather than a method. Declaring a template function to be a friend of a template class requires some special syntax - see the Implementation Hints below.
*

clear()

This method takes no arguments and returns nothing. It should properly set the stack back to the empty state. That means deleting all of the nodes in the stack and setting the top pointer back to NULL.
*

size()

This method takes no arguments and returns an integer. It should return the current size of the stack; i.e., the number of data items currently stored in the stack. Since this is not stored as a data member of the stack class, you will have to traverse the linked list and count the nodes.
*

empty()

Returns true if there are no data items currently stored in the stack; otherwise returns false.
*

top()

This method takes no arguments and returns the template parameter type. It should return the data stored in the top node of the stack (i.e., the front node in the linked list). You may assume this method will not be called if the stack is empty.
*

push()

This method takes a reference to a constant item of the template parameter type as its argument (the item to insert into the stack). It returns nothing. The method should insert the item at the top of the stack (the front of the linked list).
*

pop()

This method takes no arguments and returns nothing. It should remove the node at the top of the stack. You may assume this method will not be called if the stack is empty.

If you like, you may write private methods for the Stack class in addition to the methods described above. For example, you may want to write a copyList() method that can be called by both the copy constructor and overloaded assignment operator.
Output

A driver program, assign8.cpp is provided for this assignment. The purpose of a driver program is to test other pieces that you code. You do not need to write the driver program yourself. A copy of the driver program can also be found on turing at /home/turing/t90kjm1/CS241/Code/Spring2012/Assign7/assign7.cpp.

/*********************************************************************
PROGRAM: CSCI 241 Assignment 7
PROGRAMMER: your name
LOGON ID: your z-ID
DUE DATE: due date of assignment

FUNCTION: This program tests the functionality of the Stack
template class.
*********************************************************************/

#include
#include "Stack.h"

using std::cout;
using std::endl;

int main()
{
cout << "Testing default constructor ";

Stack s1;

cout << "s1 (size " << s1.size() << "): " << s1 << endl;
cout << "s1 is " << ((s1.empty()) ? "empty " : "not empty ");
cout << endl;

cout << "Testing push() ";

s1.push(17);

cout << "s1 (size " << s1.size() << "): " << s1 << endl;
cout << "s1 is " << ((s1.empty()) ? "empty " : "not empty ");
cout << endl;

s1.push(2);
s1.push(6);
s1.push(4);

cout << "s1 (size " << s1.size() << "): " << s1 << endl;
cout << "s1 is " << ((s1.empty()) ? "empty " : "not empty ");
cout << endl;

cout << "Testing copy constructor ";
Stack s2(s1);

cout << "s1 (size " << s1.size() << "): " << s1 << endl;
cout << "s2 (size " << s2.size() << "): " << s2 << endl << endl;

cout << "Testing clear() ";
s1.clear();

cout << "s1 (size " << s1.size() << "): " << s1 << endl;
cout << "s2 (size " << s2.size() << "): " << s2 << endl << endl;

Stack s3;

s3.push(36);
s3.push(41);
s3.push(75);
s3.push(28);

cout << "s3 (size " << s3.size() << "): " << s3 << endl << endl;

cout << "Testing assignment operator ";

Stack s4;

s4 = s3;

cout << "s3 (size " << s3.size() << "): " << s3 << endl;
cout << "s4 (size " << s4.size() << "): " << s4 << endl << endl;


s3.clear();

cout << "s3 (size " << s3.size() << "): " << s3 << endl;
cout << "s4 (size " << s4.size() << "): " << s4 << endl << endl;

cout << "Testing assignment to self ";

s4 = s4;
s3 = s4;
s4.clear();

cout << "s3 (size " << s3.size() << "): " << s3 << endl;
cout << "s4 (size " << s4.size() << "): " << s4 << endl << endl;

cout << "Testing chained assignment ";

Stack s5;

s5 = s4 = s3;

cout << "s3 (size " << s3.size() << "): " << s3 << endl;
cout << "s4 (size " << s4.size() << "): " << s4 << endl;
cout << "s5 (size " << s5.size() << "): " << s5 << endl << endl;

cout << "Testing top(), push(), pop() ";

Stack s6, s7;

for(char c = 'a'; c < 'k'; c++)
s6.push(c);

cout << "s6 (size " << s6.size() << "): " << s6 << endl << endl;

for(int i = 0; i < 10; i++)
{
int val;

val = s6.top();
s7.push(val);
s6.pop();
}

cout << "s6 (size " << s6.size() << "): " << s6 << endl;
cout << "s7 (size " << s7.size() << "): " << s7 << endl << endl;

cout << "Testing top() ";

s6 = s7;

int val1 = s6.top();
int val2 = s7.top();
val1 = s6.top(); // Make sure that top() doesn't remove a value.

cout << ((val1 == val2) ? "top() works " : "top() failure ");

cout << "Testing const correctness ";

s7.clear();
const Stack& r6 = s6;

cout << "s6 (size " << r6.size() << "): " << r6 << endl;
cout << "s6 is " << ((r6.empty()) ? "empty " : "not empty ");
cout << "Top item of s6: " << r6.top() << endl << endl;

s7 = r6;
Stack s8(r6);

cout << "s7 (size " << s7.size() << "): " << s7 << endl;
cout << "s8 (size " << s8.size() << "): " << s8 << endl << endl;

return 0;
}

Implementation Hints

*

Implement this similarly to the last assignment. Start off at the beginning of the driver program and try to get it working piece by piece. Maintain a working program as you go.
*

Declaring a template function to be a friend of a template class is one of the classic "gotcha's" in C++. We are trying to declare a function to be a friend of all classes that might be instantiated from the Stack template class, and most C++ compilers will quite properly refuse to do that without some special syntax.

The friend declaration must contain an extra set of <> to indicate that it is a template function (however, do not code this in the actual function definition - only the friend declaration). You'll also usually need to forward declare both the template class and the template function, as shown below.

How much of this you actually need to do can vary from compiler to compiler, but the code shown below works in Dev-C++ and with g++ on turing/hopper.

#ifndef STACK_H
#define STACK_H

#include

template
struct SNode
{
...

};

// Method definitions for the SNode class

// Forward declaration of the Stack template class
template
class Stack;

// Forward declaration of the operator<< template function
template
std::ostream& operator<<(std::ostream&, const Stack&);

template
class Stack
{
// friend declaration for the template function - note the
// special syntax
friend std::ostream& operator<< <>(std::ostream&, const Stack&);

...

};

// Method definitions for the Stack class

#endif /* STACK_H */

Other Points

* A Makefile is required. Same as always. Make sure it has appropriate rules for all the pieces involved. Obviously, with only one .cpp file (assign7.cpp), there won't be very many rules to write!
* Note that the driver program assumes that your header file is called Stack.h. If you name your header file differently, you'll need to modify the driver program accordingly.
* Programs that do not compile on turing/hopper automatically receive 0 points.
* Submit your program using the electronic submission guidelines posted on the course web site.

Explanation / Answer

/********************************************************************* PROGRAM: CSCI 241 Assignment 7 PROGRAMMER: your name FUNCTION: This program tests the functionality of the Stack template class. *********************************************************************/ #include #include "Stack.h" using std::cout; using std::endl; int main() { cout

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.