setting up stack functionality.

Task #1

Take the Linked List implementation that you created from Homework #2 and

add the following

member functions to create stack functionality:

1) ErrorCode pop(void) - the pop function takes the element off (erases)

from the end of the list.

ErrorCode is returned. Error checking is performed for illegal operations.

2) ErrorCode top(ListElement & x) const - the top function places the

value of the element at the end of

the list in x. ErrorCode is returned. Error checking is performed for

illegal operations.

3) void push(const ListElement x) - the push function places the

DataElement x on the end of the list.

You are provided a new StackMain.cpp file which has test cases to pass for

these new functions.

You will compile your LinkedLink.cpp and LinkedList.h with the three

provided files below.

After executing the program, the results will be output to the

Stackresults.txt file in your working directory.

You need to maintain the existing List functionality that was created in

Homework #2.

You are encouraged to use the public member functions of the LinkedLink

class to implement the

Stack member functions.

Provided files:

StackMain.cpp

MyFileIO.cpp

MyFileIO.h

Submissions for task #1:

LinkedLink.cpp

LinkedList.h

Stackresults.txt

___________________________________________________________

linkedlist.cpp

/*-- LinkedList.cpp-----------------------------------------------------------

This file implements List member functions.

-------------------------------------------------------------------------*/

#include

#include "LinkedList.h"

//--- Definition of class constructor

LinkedList::LinkedList()

: mySize(0), first(nullptr) // initialize to empty list

{

}

//--- Definition of class destructor

LinkedList::~LinkedList()

{

Node *current = first;

Node *temp;

for (int i = 0; i < mySize; i++)

{ // traverse through the list and deallocate nodes

temp = current->next; // get the next node in the linked list

delete current;

current = temp;

}

}

//--- Definition of copy constructor

LinkedList::LinkedList(const LinkedList & origList)

: mySize(origList.mySize), first(nullptr)

{

Node *temp; // stores the new node pointer

Node *prevNode = nullptr; // store the previous node pointer

Node *orgPrevNode = nullptr; // stores the previous node pointer from the original list

for (int i = 0; i < origList.mySize; i++)

{

temp = new(std::nothrow) Node();

if (temp == nullptr)

{ // if there was an error in the allocation then

std::cerr << "*** Inadequate memory to allocate storage for new node *** ";

exit(1);

}

else if (i == 0)

{ // if this is the first node then

first = temp; // set the pointer in the previous node

first->data = origList.first->data; // set the data in the node

first->next = nullptr; // set next pointer to null

prevNode = temp; // set the previous node for the next loop

orgPrevNode = origList.first; // set the org list previous node for the next loop

}

else

{

prevNode->next = temp; // set the pointer in the previous node

prevNode->next->data = orgPrevNode->next->data; // set the data in the node

prevNode->next->next = nullptr; // set next pointer to null

prevNode = temp; // set the previous node for the next loop

orgPrevNode = orgPrevNode->next; // set the org list previous node for the next loop

}

}

}

//--- Definition of assignment operator

const LinkedList & LinkedList::operator=(const LinkedList & rightHandSide)

{

if (this != &rightHandSide) // check that not self-assignment

{

// deallocate current linked list, same as the destructor code

Node *current = first;

Node *temp;

for (int i = 0; i < mySize; i++)

{

temp = current->next; // get the next node in the linked list

delete current;

current = temp;

}

// now start to copy from the rightHandSide

first = nullptr;

mySize = rightHandSide.mySize;

// similar to copy constructor

Node *prevNode = nullptr; // store the previous node pointer

Node *orgPrevNode = nullptr; // stores the previous node pointer from the original list

for (int i = 0; i < mySize; i++)

{

temp = new(std::nothrow) Node();

if (temp == nullptr)

{ // if there was an error in the allocation then

std::cerr << "*** Inadequate memory to allocate storage for new node *** ";

exit(1);

}

else if (i == 0)

{ // if this is the first node then

first = temp; // set the pointer in the previous node

first->data = rightHandSide.first->data; // set the data in the node

first->next = nullptr; // set next pointer to null

prevNode = temp; // set the previous node for the next loop

orgPrevNode = rightHandSide.first; // set the org list previous node for the next loop

}

else

{

prevNode->next = temp; // set the pointer in the previous node

prevNode->next->data = orgPrevNode->next->data; // set the data in the node

prevNode->next->next = nullptr; // set next pointer to null

prevNode = temp; // set the previous node for the next loop

orgPrevNode = orgPrevNode->next; // set the org list previous node for the next loop

}

}

}

return *this;

}

//--- Definition of isEmpty()

bool LinkedList::isEmpty() const

{ // use mySize

return (mySize == 0);

}

int LinkedList::getListSize() const

{ // use mySize

return mySize;

}

//--- Definition of display()

void LinkedList::display(std::ostream & out) const

{

Node *current = first;

for (int i = 0; i < mySize; i++)

{ // traverse through the list and display

out << current->data << " ";

current = current->next;

}

out << std::endl;

}

//--- Definition of + operator

LinkedList operator+(const LinkedList & x, const LinkedList & y)

{

LinkedList c; // create list to return

LinkedList::ListElement rv[1];

int listCount = 0; // tracks the element in list c

// get the largest list between x and y

int maxCount = x.getListSize();

if (maxCount < y.getListSize())

{

maxCount = y.getListSize();

}

for (int i = 0; i < maxCount; i++)

{ // loop through the largest list count

if (i < x.getListSize())

{ // if x still has list element then put in the list

x.getListElement(i, i, rv);

c.insert(rv[0], listCount);

listCount++;

}

if (i < y.getListSize())

{ // if xystill has list element then put in the list

y.getListElement(i, i, rv);

c.insert(rv[0], listCount);

listCount++;

}

}

return c; // return by value

}

//--- Definition of == operator

int operator==(const LinkedList & x, const LinkedList & y)

{

LinkedList::ListElement crv[1]; // temp storage

LinkedList::ListElement xrv[1];

int returnValue = 1; // default to true

if (x.getListSize() == y.getListSize())

{

LinkedList c(y); // get copy of y, use copy constructor

for (int i = 0; i < x.getListSize(); i++)

{ // loop through the x list

int count = c.getListSize();

bool found = false;

for (int j = 0; j < count; j++)

{ // look for element in c list

c.getListElement(j, j, crv);

x.getListElement(i, i, xrv);

if (crv[0] == xrv[0])

{ // if the element in the x list was found in the c list then cross it off

c.erase(j);

found = true;

break;

}

}

if (found == false)

{ // if the element from x is not found then not true

returnValue = 0; // return false

break;

}

}

}

else

{ // else lists are not equal size

returnValue = 0; // return false

}

return returnValue;

}

//--- Definition of resetList()

void LinkedList::resetList()

{

Node *current = first;

Node *temp;

for (int i = 0; i < mySize; i++)

{ // loop to deallocation elements

temp = current->next; // get the next node in the linked list

delete current;

current = temp;

}

mySize = 0; // set to empty ;ist

first = nullptr;

}

//--- Definition of insert()

LinkedList::ErrorCode LinkedList::insert(ListElement item, int pos)

{ // note pos goes from 0 to n

if (pos < 0 || pos > mySize)

{ // perform error checking on the input

return ILLEGAL_LIST_POSITION;

}

// get the new node to insert

Node *temp = new(std::nothrow) Node();

if (temp == nullptr)

{ // if there was an error in the allocation then

std::cerr << "*** Inadequate memory to allocate storage for new node *** ";

exit(1);

}

temp->data = item;

temp->next = nullptr; // if at the end of the list

if (pos == 0)

{ // process insertion at the beginning of the list

temp->next = first;

first = temp;

}

else

{ // process insertion after the beginning of the list

// find the node before the insertion point

Node *current = first;

for (int i = 1; i < pos; i++)

{

current = current->next;

}

temp->next = current->next; // set the next pointer in the new node

current->next = temp; // set the next pointer in the previous node

}

mySize++; // increase list size

return NO_ERROR;

}

//--- Definition of erase()

LinkedList::ErrorCode LinkedList::erase(int pos)

{

if (mySize == 0)

{ // perform error checking on the input

return ILLEGAL_LIST_POSITION;

}

if (pos < 0 || pos >= mySize)

{ // perform error checking on the input

return ILLEGAL_LIST_POSITION;

}

Node *temp;

if (pos == 0)

{ // if the deletion is the zero node then

temp = first; // save pointer to be deleted

first = first->next; // bypass node

delete temp; // delete node

mySize--; // decrease list size

}

else

{

// find the node before the deletion point

Node *current = first;

for (int i = 1; i < pos; i++)

{

current = current->next;

}

temp = current->next; // save pointer to be deleted

if (pos == (mySize - 1))

{ // if the deleted node is at the end of the list then

current->next = nullptr;

}

else

{ // else there is another node to link with

current->next = current->next->next;

}

delete temp; // delete the node

mySize--; // decrease list size

}

return NO_ERROR;

}

LinkedList::ErrorCode LinkedList::move(int n, int m)

{

if (n < 0 || m < 0 || n >= mySize || m >= mySize)

{ // perform error checking on the input

return ILLEGAL_LIST_POSITION;

}

if (m == n) // nothing to move

return NO_ERROR;

Node *temp;

if (n == 0)

{ // if the move is from zero node then

temp = first; // save pointer to be moved

first = first->next; // bypass node

}

else

{

// find the node before the deletion point

Node *current = first;

for (int i = 1; i < n; i++)

{ // traverse to the node

current = current->next;

}

temp = current->next; // save pointer to be moved

if (n == (mySize - 1))

{ // if the deleted node is at the end of the list then

current->next = nullptr;

}

else

{ // else there is another node to link with

current->next = current->next->next;

}

}

// now insert the moved node temp

if (m == 0)

{ // process insertion at the beginning of the list

temp->next = first;

first = temp;

}

else

{ // process insertion after the beginning of the list

// find the node before the insertion point

Node *current = first;

for (int i = 1; i < m; i++)

{

current = current->next;

}

temp->next = current->next; // set the next pointer in the new node

current->next = temp; // set the next pointer in the previous node

}

return NO_ERROR;

}

void LinkedList::reverse()

{

if (mySize >= 2)

{ // if the list is large enough to reverse then

int numOfSwaps = (int)(mySize / 2);

for (int i = 0; i < numOfSwaps; i++)

{ // keep swapping the ends of the list

move(i, (mySize-1)-i);

move((mySize - 2) - i, i);

}

}

}

//--- Definition of getListElement()

LinkedList::ErrorCode LinkedList::getListElement(int posStart, int posEnd, ListElement rv[]) const

{

if (posStart < 0 || posStart >= mySize || posEnd < 0 || posEnd >= mySize || posStart > posEnd)

{ // check for valid paramenters

return ILLEGAL_LIST_POSITION;

}

Node *current = first; // point to zero node

for (int i = 0; i < posStart; i++)

{ // loop to find the node

current = current->next;

}

for (int i = 0; i < ((posEnd - posStart)+1); i++)

{ // put returned elements in the beginning of the list

rv[i] = current->data;

current = current->next;

}

return NO_ERROR;

}

__________________________________________________

linkedlist.h

/*-- LinkedList.h --------------------------------------------------------------

This header file defines the data type List for processing lists.

Operations are:

Constructor

Destructor

Copy constructor

Assignment operator

isEmpty: Check if list is empty

resetList: Empties a list

insert: Insert an item

erase: Remove an item

getListSize: Get the size of the list

getListElement: get a range of list elements

move: move an element from one position to another

reverse: reverse the list

+ operator overload

== operator overload

display: Output the list

-------------------------------------------------------------------------*/

#include

#ifndef LINKED_LIST_H

#define LINKED_LIST_H

class LinkedList

{

public:

typedef int ListElement;

private:

/******** Data Members ********/

class Node

{

public:

ListElement data;

Node * next;

};

Node *first; // pointer to first element in linked list

int mySize; // current size of list

public:

/******** Error Codes ********/

enum ErrorCode { ILLEGAL_LIST_POSITION = -1, NO_ERROR = 0 };

/******** Function Members ********/

/***** Class constructor *****/

/*----------------------------------------------------------------------

Construct a List object.

Precondition: None.

Postcondition: An empty List object is constructed; first ==

nullptr and mySize is 0.

-----------------------------------------------------------------------*/

LinkedList();

/***** Class destructor *****/

/*----------------------------------------------------------------------

Destroys a List object.

Precondition: The life of a List object is over.

Postcondition: The memory dynamically allocated by the constructor

for the array pointed to by myArray has been returned to the heap.

-----------------------------------------------------------------------*/

~LinkedList();

/***** Copy constructor *****/

/*----------------------------------------------------------------------

Construct a copy of a List object.

Precondition: A copy of origList is needed; origList is a const

reference parameter.

Postcondition: A copy of origList has been constructed.

-----------------------------------------------------------------------*/

LinkedList(const LinkedList & origList);

/***** Assignment operator *****/

/*----------------------------------------------------------------------

Assign a copy of a List object to the current object.

Precondition: rightHandSide List is required.

Postcondition: A copy of rightHandSide has been assigned to this

object. A const reference to this list is returned.

-----------------------------------------------------------------------*/

const LinkedList & operator=(const LinkedList & rightHandSide);

/***** isEmpty operation *****/

/*----------------------------------------------------------------------

Assign a copy of a List object to the current object.

Precondition: A constructed list, either empty or with elements.

Postcondition : return true if empty, otherwise false.

-----------------------------------------------------------------------*/

bool isEmpty() const;

/***** mutators *****/

/***** reset list operation *****/

/*----------------------------------------------------------------------

empty the current list and deallocate all list elements.

Precondition: A constructed list, either empty or with elements.

Postcondition : an empty list (no element in the list), all elements are deallocated

-----------------------------------------------------------------------*/

void resetList();

/***** insert operation *****/

/*----------------------------------------------------------------------

Insert item at pos position. pos 0 is the first element position in the list

Precondition: A constructed list, either empty or with elements

Postcondition : inserted item into list at pos position

Returns ILLEGAL_LIST_POSITION for insert that is out of range of the current list,

Otherwise return a NO_ERROR.

-----------------------------------------------------------------------*/

ErrorCode insert(ListElement item, int pos);

/***** erase operation *****/

/*----------------------------------------------------------------------

Erase item at pos position. pos 0 is the first element position in the list.

Precondition: A constructed list, either empty or with elements

Postcondition : erased item at pos position

Returns ILLEGAL_LIST_POSITION for erase that is out of range of the current list,

Otherwise return a NO_ERROR.

-----------------------------------------------------------------------*/

ErrorCode erase(int pos);

/***** move operation *****/

/*----------------------------------------------------------------------

Move item from position n to position m

Precondition: A constructed list, either empty or with elements

Postcondition : item is moved from n to m position

Returns ILLEGAL_LIST_POSITION for move that is out of range of the current list,

Otherwise return a NO_ERROR.

-----------------------------------------------------------------------*/

ErrorCode move(int n, int m);

/***** reverse operation *****/

/*----------------------------------------------------------------------

Reverse items in a list

Precondition: A constructed list, either empty or with elements.

Postcondition : List items are now in reverse order.

-----------------------------------------------------------------------*/

void reverse();

// Accessors

/***** getListElement *****/

/*----------------------------------------------------------------------

Returns a list element at position pos

Precondition: A constructed list, either empty or with elements.

The rv[] array must be large enough to hold the returned contents.

Postcondition : Fills array rv with the list elements specified

Returns ILLEGAL_LIST_POSITION for move that is out of range of the current list,

Otherwise return a NO_ERROR. Both posStart and posEnd must be valid positions

and posStart <= posEnd. posStart is an index to the start of the data and

posEnd is an index to the end of the data. To retieve one element

posStart and posEnd will be the same value.

-----------------------------------------------------------------------*/

ErrorCode getListElement(int posStart, int posEnd, ListElement rv[]) const;

/***** getListSize *****/

/*----------------------------------------------------------------------

Returns the list size

Precondition: A constructed list, either empty or with elements.

Postcondition : Returns the list size

-----------------------------------------------------------------------*/

int getListSize() const;

/***** output *****/

/*----------------------------------------------------------------------

Display items in a list

Precondition: open output stream, A constructed list, either empty or with elements.

Postcondition : items in list are displayed to console

-----------------------------------------------------------------------*/

void display(std::ostream & out) const;

}; //--- end of List class

/***** operator + overload *****/

/*----------------------------------------------------------------------

define the + operator

Precondition: two lists x and y

Postcondition : return a merged addition list

-----------------------------------------------------------------------*/

LinkedList operator+(const LinkedList & x, const LinkedList & y);

/***** operator == overload *****/

/*----------------------------------------------------------------------

define the == operator

Precondition: two lists x and y

Postcondition : return of 1 if true, otherwise false

-----------------------------------------------------------------------*/

int operator==(const LinkedList & x, const LinkedList & y);

#endif