In C++, implement a Linked List-based Stack called LinkedListStack. When the sta
ID: 3885296 • Letter: I
Question
In C++, implement a Linked List-based Stack called LinkedListStack. When the stack is full, its size can grow as elements are inserted into the stack. Use the template Stack.h to create LinkedListStack using templates for Linked List, filling in all of the member functions. Another class for nodes will need to be created as well. Your code should be able to be complied and LinkedListStack should be a .h file. fill in all member functions just as they appear in Stack.h. Use names given in Stack.h. LinkedListStack.h should start like this:
#ifndef LinkedListStack_h
#define LinkedListStack_h
#include "Stack.h"
#include
template
class LinkedListStack : public AbstractStack
{...};#endif
Use this as a template and and to know what member functions need to be created
Stack.h
#ifndef ABSTRACT_STACK_H
#define ABSTRACT_STACK_H
#include
using namespace std;
template
class AbstractStack
{
private:
// data goes here
public:
AbstractStack(void) {}
~AbstractStack(void) {}
bool isEmpty(void) {}
int size(void) {}
Type top() throw(exception) {}
Type pop() throw(exception) {}
void push ( Type e ) {}
};
#endif
Explanation / Answer
LinkedList.h
#ifndef LINKEDLIST_H
#define LINKEDLIST_H
#include <iostream>
template <class T>
class LinkedList
{
public:
T m_data; // Data to be stored
LinkedList<T>* m_next; // Pointer to the next element in the list
// Purpose: Default constructor
// Postconditions: next pointer set to NULL
// ---INLINE---
LinkedList() : m_next(NULL) {}
// Purpose: Auxiliaty constructor, construct from parameters
// useful when inserting elements
// Postconditions: data and next pointer set to parameters
// ---INLINE---
LinkedList(const T& x, LinkedList<T>* p)
: m_data(x), m_next(p) {}
// --------
// ---- Big 3 Member Functions ---
// --------
// Purpose: Destructor
// IMPORTANT:: For didactic purposes, the destructor is left empty.
// YOU are expected to implement function clear() to de-allocate the list
// --INLINE
~LinkedList() {}
// Purpose: performs a deep copy of the data from rhs into this linked list
// Parameters: rhs is linked list to be copied
// Returns: *this
// Postconditions: this list contains same data values (in the same order)
// as are in rhs; any memory previously used by this list has been
// deallocated.
const LinkedList<T>& operator= (const LinkedList<T>& rhs);
// Purpose: copy constructor
// Parameters: rhs is the LinkedList that is to be copied
// Postconditions: this list contains same data values (in same order)
// as in rhs.
LinkedList(const LinkedList<T>& rhs);
// --------
// ---- Basic Accessor Operations ---
// --------
// Purpose: accessor function for the current # data values in the list
// Returns: current size of the list
int size() const;
// Purpose: determines whether the list is empty
// Returns: 'true' if list is empty; 'false' otherwise
bool isEmpty() const;
// Purpose: Get a pointer to the first element node
// Returns: pointer to the first node in the list;
// returns NULL if the list is empty
LinkedList<T>* getFirstPtr();
// Purpose: accessor function for last element node
// Returns: pointer to the last element's node in the list;
// returns NULL if list is empty
LinkedList<T>* getLastPtr();
// Purpose: accessor function for a node in the list
// Returns: pointer to the node at the i'th position in the list;
// returns NULL if no such element exists.
LinkedList<T>* getAtPtr(int i);
// --------
// ---- Basic Mutator Operations ---
// --------
// Purpose: effectively "empties" the list
// Postconditions: all dynamically allocated memory for nodes deallocated
void clear();
// Purpose: puts the data x in the front of the list
// Parameters: x is data value to inserted
// Postconditions: x is the first element of the list
void insert_front(const T& x);
// Purpose: puts the data value x at the position pointed by pos
// Parameters: x is data value to inserted
// pos pointer to the position to insert x at.
// Preconditions: pos is a pointer in this list.
// Postconditions: x is inserted at the position pointed by pos
void insert(const T& x, LinkedList<T>* pos);
// Purpose: removed the element in the position pointed by pos
// Parameters: pos pointer to the position to remove.
// Preconditions: pos is a pointer in this list.
// Postconditions: position pointed by pos is removed from the list
void remove(LinkedList<T>* pos);
// --------
// ---- Complex Operations ---
// --------
// Purpose: determines whether this list is identical to rhs list in
// terms of data values and their order in the list
// Parameters: rhs is list to be compared to this list
// Returns: true if lists are identical; otherwise, false
bool operator== (const LinkedList<T>& rhs) const;
// Purpose: determines whether x is in the list
// Parameters: x is data value to be found
// Returns: a pointer to the position of x in the list;
// otherwise, NULL
LinkedList<T>* find(const T& x);
// Purpose: reverses the elements from the list
// Postconditions: the list is now in reverse order
void reverse();
// Purpose: appends two lists
// Parameters: xlist, a list to append to the end of 'this' list
// Postconditions: elements of alist are appended to 'this' list
void append(const LinkedList<T>& xlist);
}; // of class LinkedList
// --------------- Utility Function for Printing
// Purpose: prints a LinkedList
template <typename T>
std::ostream& operator<< (std::ostream& out, const LinkedList<T>& xlist)
{
out << "[ ";
const LinkedList<T>* p = &xlist;
while ( p->m_next != NULL ){
out << p->m_data << ", ";
p = p->m_next;
}
out << "]";
return out;
}
#include "LinkedList.hpp"
#endif
LinkedList.hpp
template <typename T>
const LinkedList<T>& LinkedList<T>::operator = (const LinkedList<T>& rhs)
{
if(this != &rhs)
{
LinkedList<T>* p = this;
int size = rhs.size();
clear();
const LinkedList<T>* ptr = &rhs;
for(int i = 0; i < size; i++)
{
p->m_data = ptr->m_data;
ptr = ptr->m_next;
p->m_next = new LinkedList<T>;
p = p->m_next;
}
}
return *this;
}
template <typename T>
LinkedList<T>::LinkedList(const LinkedList<T>& rhs)
{
m_next = new LinkedList<T>();
*this = rhs;
}
template <typename T>
int LinkedList<T>::size() const
{
//If we've hit the sentinel node
if(m_next == NULL)
{
return 0;
}
return m_next->size() + 1;
}
template <typename T>
bool LinkedList<T>::isEmpty() const
{
return m_next == NULL;
}
template <typename T>
LinkedList<T>* LinkedList<T>::getFirstPtr()
{
if(m_next == NULL)
{
std::cout << "Panic in LinkedList.getFirstPtr()! Empty List!" << std::endl;
return NULL;
}
return this;
}
template <typename T>
LinkedList<T>* LinkedList<T>::getLastPtr()
{
if(m_next != NULL && m_next -> m_next == NULL)
{
return this;
}
else if(m_next == NULL)
{
std::cout << "Panic in LinkedList.getLastPtr()! Empty List!" << std::endl;
return NULL;
}
return m_next -> getLastPtr();
}
template <typename T>
LinkedList<T>* LinkedList<T>::getAtPtr(int i)
{
int size = this->size();
if(i >= size || i < 0)
{
std::cout << "Panic in LinkedList.getAtPtr(). " << i << " is an invalid index!" << std::endl;
return NULL;
}
LinkedList<T>* p = this;
for(int j = 0; j < i; j++)
{
p = p -> m_next;
}
return p;
}
template <typename T>
void LinkedList<T>::clear()
{
if(m_next != NULL)
{
m_next -> clear();
delete m_next;
m_next = NULL;
}
}
template <typename T>
void LinkedList<T>::insert_front(const T& x)
{
insert(x, this);
}
template <typename T>
void LinkedList<T>::insert(const T& x, LinkedList<T>* pos)
{
LinkedList<T>* p = new LinkedList<T>;
p->m_data = pos->m_data;
pos->m_data = x;
p->m_next = pos->m_next;
pos->m_next = p;
p = NULL;
}
template <typename T>
void LinkedList<T>::remove(LinkedList<T>* pos)
{
LinkedList<T>* p = getFirstPtr();
while(p->m_next != NULL && p->m_next != pos)
{
p = p->m_next;
}
p->m_next = pos->m_next;
pos->m_next = NULL;
delete pos;
pos = NULL;
}
template <typename T>
bool LinkedList<T>::operator == (const LinkedList<T>& rhs) const
{
const LinkedList<T>* a = this;
const LinkedList<T>* b = &rhs;
while((a -> m_next != NULL && a -> m_next -> m_next != NULL) &&
(b -> m_next != NULL && b -> m_next -> m_next != NULL))
{
if(a -> m_data != b -> m_data)
{
return false;
}
a = a->m_next;
b = b->m_next;
}
return true;
}
template <typename T>
LinkedList<T>* LinkedList<T>::find(const T& x)
{
LinkedList<T>* p = this;
while(p->m_data != x && p->m_next != NULL)
{
p = p->m_next;
}
return p;
}
template <typename T>
void LinkedList<T>::reverse()
{
LinkedList<T>* temp = new LinkedList<T>;
LinkedList<T>* p = this;
while(p->m_next != NULL)
{
temp->insert_front(p->m_data);//(*temp).insert_front((*p).m_data);
p = p->m_next;
}
*this = *temp;
temp->clear();
delete temp;
}
template <typename T>
void LinkedList<T>::append(const LinkedList<T> & xlist)
{
LinkedList<T>* p = getLastPtr();
const LinkedList<T>* ptr = &xlist;
delete p->m_next;
p->m_next = new LinkedList<T>;
p = p->m_next;
while(ptr->m_next != NULL)
{
p->m_next = new LinkedList<T>;
p->m_data = ptr->m_data;
ptr = ptr->m_next;
p = p->m_next;
}
}
LinkedListStack.h
#ifndef LINKEDLISTSTACK_H
#define LINKEDLISTSTACK_H
#include "abstractstack.h"
#include "LinkedList.h"
template <typename T>
class LinkedListStack : public AbstractStack<T>
{
public:
LinkedList<T>* next;
int size;
LinkedListStack() : next(NULL), size(0) {}
~LinkedListStack();
// Purpose: clears the stack
// Postconditions: the stack is now empty
void clear();
// Purpose: push an element into the stack
// Parameters: x is the value to push into the stack
// Postconditions: x is now the element at the top of the stack,
void push(const T& x);
// Purpose: pop the stack
// Postconditions: the element formerly at the top of the stack has
// been removed
// Note: Poping an empty stack results in an empty stack.
void pop();
// Purpose: looks at the top of the stack
// Returns: a const reference to the element currently on top of the stack
// Exception: if the stack is empty, THROW a 'Oops' object with an error message!!!
const T& top() const throw ( Oops );
// Purpose: Checks if a stack is empty
// Returns: 'true' if the stack is empty
// 'false' otherwise
bool isEmpty() const;
};
#include "LinkedListStack.hpp"
#endif // LINKEDLISTSTACK_H
LinkedListStack.hpp
template <typename T>
void LinkedListStack<T>::clear()
{
if(size != 0)
{
next -> clear();
}
size = 0;
}
template <typename T>
bool LinkedListStack<T>::isEmpty() const
{
return size == 0;
}
template <typename T>
void LinkedListStack<T>::pop()
{
if(size > 1)
{
LinkedList<T>* p = next;
next = p->m_next;
delete p;
p = NULL;
}
else if(size == 1)
{
delete next;
next = NULL;
}
size--;
}
template <typename T>
void LinkedListStack<T>::push(const T& x)
{
if(next == NULL)
{
next = new LinkedList<T>;
next->m_data = x;
}
else
{
LinkedList<T>* p = new LinkedList<T>;
p->m_data = x;
p->m_next = next;
next = p;
p = NULL;
}
size++;
}
template <typename T>
const T& LinkedListStack<T>::top() const throw (Oops)
{
if(size != 0)
{
return next -> m_data;
}
throw new Oops("You can't see the top of an empty Stack!");
}
template <typename T>
LinkedListStack<T>::~LinkedListStack()
{
if(next != NULL)
{
next -> clear();
}
}
abstractstack.h
#ifndef ABSTRACTSTACK_H
#define ABSTRACTSTACK_H
#include <string>
using namespace std;
/*
Class 'Oops'
Thrown when an error is encountered.
Member 'm_msg' stores an error message.
*/
class Oops
{
public:
string m_errormsg;
Oops(string msg) : m_errormsg(msg) {}
};
template < typename T >
class AbstractStack
{
public:
// Purpose: clears the stack
// Postconditions: the stack is now empty
virtual void clear() = 0;
// Purpose: push an element into the stack
// Parameters: x is the value to push into the stack
// Postconditions: x is now the element at the top of the stack,
virtual void push(const T& x) = 0;
// Purpose: pop the stack
// Postconditions: the element formerly at the top of the stack has
// been removed
// Note: Poping an empty stack results in an empty stack.
virtual void pop() = 0;
// Purpose: looks at the top of the stack
// Returns: a const reference to the element currently on top of the stack
// Exception: if the stack is empty, THROW a 'Oops' object with an error message!!!
virtual const T& top() const throw ( Oops ) = 0;
// Purpose: Checks if a stack is empty
// Returns: 'true' if the stack is empty
// 'false' otherwise
virtual bool isEmpty() const = 0;
};
#endif