0

I'm trying to write a class representing a Stack object in C++ using templates. This stack object will hold as data 'EToll' objects, which represent cars in the real world.

This is for a university task, and some restrictions have been placed on me. They are as follows:

The Stack must:

  1. be built by 'wrappering' around a LinkedList (essentially I've just included a "LinkedList" as a private member for stack and built it's functions based on functions inside a LinkedList class I wrote).
  2. printing or removing elements from the stack must be done via methods within the stack (eg push(), pop(), etc.) and cannot just call print or remove methods from LinkedList.

The stack cannot:

  1. use keywords 'struct' or 'friend'
  2. reveal internal structure (such as by returning 'data' publicly)

With that out of the way, let me explain what I'm trying to do. I want to output the entire contents of a stack object by overloading the stream insertion operator (ie '<<'). I'm aware the way Stacks are built make this rather inconvenient, but this is one of the requirements of the task. This is my code for the '<<' operator overload:

template <typename T>
ostream& operator << (ostream& out, LStack<T>& LS)
{
  if (LS.isEmpty())
  {
    out << "List is empty.";
  } else
  {
    LStack<T> LScopy;
    LScopy = LS.copy(LS); //ensures original input LS remains unmodified

    while (!(LScopy.isEmpty()))
    {
      out << "(";
      out << LScopy.peek().get_licence();
      out << ", ";
      out << LScopy.peek().get_charge();
      out << ") ";
      LScopy.pop(); //continues the traversal of LScopy
    }

    //delete LS copy here to prevent memory leak

    return out;
  }
}

I need a copy function to ensure the input 'LS' doesn't get modified within the '<<' overload. I have next to no experience with copy functions or templates, so I am lost as to how to make my copy function. Other threads trying to achieve similar things (eg C++ Creating a copy constructor for stack class ) have not worked. memcpy has not worked either. Here is what I've tried to do with my copy function:

//returns a copy of parameter 'src' as a LinkedList<T>&
template <typename T>
LStack<T>& LStack<T>::copy(LStack<T>& src)
{
  LStack<T>* srcCopy = new LStack<T>();

  //copying contents of src to srcCopy
  memcpy(srcCopy, src, sizeof(src));

  //returning the copied LStack
  return srcCopy;
}

Here's the basic code for my stack class (haven't included full thing for sake of brevity):

//start macroguard
#ifndef LSTACK_H
#define LSTACK_H

#include "LinkedList.h"
#include <x> <y> <z> etc ...

template <typename T>
class LStack 
{
public: 
  //constructor:
  LStack();

  //Destructor:
  ~LStack();

  //push - adds item to top of stack
  void push(T& obj);

  //copy function - not working at present
  LStack<T>& copy(LStack<T>& src);

  //pop - removes and returns item at top of Stack. If
  //stack is empty, do nothing
  T pop();

  //peek - returns item at top of stack
  T& peek();

  //size - returns number of items in the stack
  int size() const;

  //isEmpty - indicates if the stack has 0 or >0 items
  bool isEmpty();

private: 
  LinkedList<T> data;
};

//'<<' operator overload - prints all items in stack
template <typename T>
ostream& operator << (ostream&, LStack<T>& LS);

#include "LStack.hpp"
#endif //end of macroguard

Here's the basic code for my LinkedList class:

//start macroguard
#ifndef LINKEDLIST_H
#define LINKEDLIST_H

#include "Node.h"
#include <x> <y> <z> etc...

template <typename T>
class LinkedList
{
public:

  //Constructor: 
  LinkedList();

  //Destructor:
  ~LinkedList();

  //addToHead - adds an item to head of list
  void addToHead(T& item);

  //addToTail - adds an item to tail of list
  void addToTail(T& item);

  //removeNode - calls relevant function if parameter 
  //'nodeToRemove' was head or tail. otherwise, removes 
  //an internal node from the list.
  void removeNode(Node<T>* nodeToRemove);

  //removeFromHead - removes an item from head of list
  void removeFromHead();

  //removeFromTail - removes an item from tail of list
  void removeFromTail();

  //length - returns number of Nodes in list
  int length();

  //isEmpty - indicates whether list has 0 or >0 items
  bool isEmpty();

  //getHead - returns 'data' value of list's head
  T& getHead();

  //getTail - returns 'data' value of list's tail
  T& getTail();

  //getCurrentData - returns 'data' value of list's 
  //'current' pointer
  T& getCurrentData();

  //moveCurrentForward - moves 'current' pointer to 
  //next node
  void moveCurrentForward();

  //moveCurrentBackward - moves 'current' pointer to 
  //previous node
  void moveCurrentBackward();

  //moveCurrentToHead - moves 'current' pointer to 
  //list's head
  void moveCurrentToHead();

  //moveCurrentToTail - moves 'current' pointer to 
  //list's tail
  void moveCurrentToTail();

private:
  Node<T>* head;
  Node<T>* tail;
  Node<T>* current; //used when traversing list

};

template <typename T>
ostream& operator << (ostream& out, LinkedList<T>& LL);

#include "LinkedList.hpp"
#endif //end of macroguard

Finally the basic code for my Node class:

#ifndef NODE_H
#define NODE_H
#include "EToll.h"
#include <x> <y> <z> etc....

template <typename T>
class Node 
{

public: 
  //Constructors
  Node(); //default

  //i = data item, n = next, p = prev
  Node(const T& i, Node* n, Node* p); //detailed constructor

  //destructor
  ~Node();

  //set_next - sets the next value of Node
  void set_next(Node* next_ptr);

  //set_prev - same as above

  //set_data - sets the data value of Node
  void set_data(const T& new_data);

  //get_next - returns the next value of Node


  //get_prev - same as above

  //get_data - returns the data value of Node
  T& get_data();

private: 
  Node* next;
  Node* prev;
  T data;

};

#include "Node.hpp"
#endif

Final notes:

  1. Please forgive any glaring issues like memory leaks or unoptimised programming decisions. I am a novice with Data Structures. Also I am new to C++ - I come from Java where everything is much simpler. My goal right now is "make sure everything just works now and fix issues later".
  2. If you need any extra code or explanation why I've done certain things, ask and I will provide it to you.

Thanks a lot for any help.

Ken White
  • 123,280
  • 14
  • 225
  • 444
  • you should add th C++ tag – tttony Oct 06 '21 at 23:44
  • XY problem. You don't need to copy the stack to output it. Think again. – user207421 Oct 07 '21 at 01:02
  • You could look at some of the code review examples of people implementing a linked list: https://codereview.stackexchange.com/q/125955/507 – Martin York Oct 07 '21 at 01:12
  • The above is 100% true. But the current state of the question gives me an opportunity to go on a [Rule of Three](https://en.cppreference.com/w/cpp/language/rule_of_three) rant. Don't write a copy function. Do the C++ thing and write proper Copy Constructors and Assignment Operators. If you need to. If you don't, embrace the Rule of Zero. The general rule of thumb is use the Rules of Three or Five as close to a resource that needs protecting as possible and use the Rule of Zero on everything that builds on top of that resource's wrapper. – user4581301 Oct 07 '21 at 01:13
  • As for the copy function... You cannot use `memcpy` on a complex class, and because `LStack` contains a `LinkedList`, a mess of owning pointers, it's too complex. `memcpy` will copy the addresses in `LinkedList`, not the pointed-at `Node`s, and now you have two `LinkedList`s pointing at the same `Nodes`. Change one and it will look like you changed both. Because you did. When one of them goes out of scope and the destructor deletes the `Node`s while cleaning up, the `LinkedList` that wasn't destroyed is left pointing to garbage. The program is now doomed to an ill fate sooner or later. – user4581301 Oct 07 '21 at 01:14
  • A note on [owning pointers](https://stackoverflow.com/questions/49024982/what-is-ownership-of-resources-or-pointers) – user4581301 Oct 07 '21 at 01:15
  • 1
    *"I need a copy function to ensure the input 'LS' doesn't get modified within the '<<' overload."* -- If you want to ensure that `LS` is not modified, it should be taken by `const` reference. So now I'm wondering -- who decided on the signature for `operator<<`? If it was given to you, it might be intended that `LS` is *restored* to its original state rather than not modified. (What I'm thinking of is not the best approach, but then again not taking advantage of the underlying linked list is not necessarily the best approach either. It might have an educational goal, though. Hence, I ask.) – JaMiT Oct 07 '21 at 02:05
  • @JaMiT yes you are correct, my Professor originally gave me the signature for the '<<' operator. The one he gave did have the const qualifier, was just my bad I forgot to include it, thanks for bringing it to my attention. – Daniel Dinosaur Oct 07 '21 at 04:26
  • @JaMiT but now I am faced with multiple fpermissive (discards const qualifier) compiler errors - I've added const to most of the functions I could, but not sure how to change the signatures of functions within LinkedList to add the 'const' qualifier, eg 'void LinkedList:: moveCurrToHead()'. Right now the compiler is trying to apply a non const function to a const obj, and it cannot. How do I change these types of signatures to work with const objects? – Daniel Dinosaur Oct 07 '21 at 04:29
  • @DanielDinosaur What you're seeing is that correct `const`-qualification is a pain to retrofit into code. (It's easier if done from the start. ;) ) Unfortunately, this is not a good place to discuss the process. The main guideline is to use `const` on every member function that does not change an object's data, like you did for `LStack::size()`. (Your `current` member is probably going to mess with that for your list, though -- does traversing a list count as changing the data?) – JaMiT Oct 08 '21 at 01:28

0 Answers0