# Stack implemented with linked list

I have looked at some previous posts and changed my code accordingly. Do you have some suggestions about my current code?

Here are my specific questions:

1. What should top() return if the stack is empty?

2. Why it’s better to use size_t for count?

3. I didn’t use new to create the stack in main(). Do I need to call the destructor? If no, why? If yes, how should I do it?

4. According to the rule of three, how will I define the assignment operator for stack? Can you give one example?

5. I feel I have some misunderstanding about private. I put top_node in the private section, but why I am able to access top_node in the copy constructor?

The following code compiles and runs.

#include<iostream>
using namespace std;

template<class T>
class MyStack{
public:
MyStack(): top_node(nullptr), count(0){};

MyStack(MyStack& st){
top_node = new Node(st.top());
Node* temp = st.top_node->next;
Node* pre = top_node;
while(temp){
Node* cur = new Node(temp->val);
pre->next = cur;
temp = temp->next;
}
count = st.size();
}

void push(T item){
Node* temp = new Node(item);
if(empty()){
top_node = temp;
}else{
temp->next = top_node;
top_node = temp;
}
count++;
}

void pop(){
if(empty()){
cout<<"Nothing to pop!"<<endl;
return;
}
Node* temp = top_node;
top_node = temp->next;
delete temp;
}

int top() const{
if(empty()){
cout<<"Nothing to top!"<<endl;
return -1;
}
}

size_t size() const{
return count;
}

void print() const{
Node* temp = top_node;
while(temp){
cout<<temp->val<<" ";
temp = temp->next;
}
cout<<endl;
}

bool empty() const{
return count==0;
}

~MyStack(){
Node* temp = top_node;
while(temp){
Node* t = temp;
temp = temp->next;
delete t;
}
top_node = nullptr;
}

private:
struct Node{
T val;
Node* next;
Node(T x): val(x), next(nullptr){};
};
Node* top_node;
size_t count;

};

int main(){

MyStack<char> sasa;
cout<<"default top: "<<sasa.top()<<endl;
cout<<"default count: "<<sasa.size()<<endl;

sasa.pop();
sasa.push('a');
sasa.push('p');
sasa.push('p');
sasa.print();
sasa.top();
cout<<"The current size is "<<sasa.size()<<endl;
sasa.pop();
sasa.print();
cout<<"if empty: "<<sasa.empty()<<endl;

MyStack<char> sec(sasa);
sec.print();

return 0;
}

• Which C++ version is this targeting? You might get better reviews if we know what to look for. – hoffmale Aug 5 '18 at 21:35
• @ hoffmale, C++11 – Lusha Li Aug 5 '18 at 21:47
• While your code works and is reviewable here, your "specific questions" would be better addressed on Stack Overflow. – 1201ProgramAlarm Aug 6 '18 at 0:30

# Implementation issues

• using namespace std; is frowned upon, especially in header files. Assuming MyStack is intended to be included elsewhere, this might cause name collisions in other unrelated code.

• There's a superfluous (and possibly confusing) semicolon after default constructor.

• Memory leak: If something inside the copy constructor were to throw an exception (e.g. one of those calls to new), already created nodes will not be deleted.

• Another memory leak/bug in the copy constructor: pre doesn't get advanced during the while loop, so it's always pointing to top_node. Every assignment pre->next = cur overwrites the current value of top_node->next, resulting in a stack of depth 2.

• Also, since the copy constructor doesn't modify st, it could be made const MyStack&.

• Memory leak: MyStack<T>::push leaks temp in case the Node constructor throws an exception (e.g. because Ts copy constructor throws one).

• Wrong return type: MyStack::top() is declared to return an int, but actually returns MyStack<T>::Node::val, which is of type T.

• No need for top_node = nullptr inside the destructor: Nobody is going to read that value again.

• The whole destructor body could be extracted into a clear member function, which the destructor then calls.

• A lot of the member functions (basically everything not calling new) can be marked noexcept. Doing so allows for better code generation and allows others to use MyStack to its fullest.

• pop doesn't decrease count.

# Design issues

• MyStack::print might be helpful with debugging, but likely shouldn't be in the final product (unless there is a specific requirement for it).

print can likely be very easily implemented using an iterator interface if one is provided.

• MyStack is unable to contain types that cannot be copy-constructed. Think about splitting push(T) into two functions push(const T&) and push(T&&), and maybe add an emplace member function that forwards its arguments in order to construct the T in place.

• top could return a referene instead of a copy. This prevents issues with non-copyable types. Might require two overloads, though (const T& top() const and T& top()), to accomodate for constness of this.

• Technically, MyStack<T> can be copied only if T is copy-constructible. This can be asserted at compile time using some template metaprogramming (which might be too advanced at the moment), but at the very least I'd expect this behavior to be documented.

# C++11 features

C++11 introduced smart pointer like std::unique_ptr and std::shared_ptr into the standard library. You might want to read up on them, as they come in quite handy and help a lot to prevent memory leaks. Just know their limits (recursive destruction/cycles).

Using them would have prevented a lot of the memory issues mentioned above. For more information on the topic I can recommend this talk by Herb Sutter.

Also, C++11 introduced {} for object initialization, in order to "fix" the so-called most vexing parse: What is foo in the following snippet?

int foo(A);


That answer depends on what A is:

• If A can be interpreted as a type then foo is declared as a function taking an A as parameter and returning an int.

• If A is a value then foo is a local int variable that gets initialized to the value of A.

In order to prevent this ambiguity (and a huge list of similar ones) prefer to use brackets {} for object initialization instead of () if possible.

There are some cases where this isn't possible; however, those cases are rare (I can only think of one off my head, and that's the std::vector<T>::vector(size_t, T) constructor where T is some arithmetic type like int or float, as the initializer-list constructor takes precedence there).

# Q&A

1. What should top() return if the stack is empty?

What can it meaningfully return? Nothing!

The precondition of calling top is that the stack must not be empty. If top is called while the stack is empty, that operation is meaningless. You can be nice and throw an exception to signal that this function was called erroneously, or not be nice and force checking upon the caller in order to avoid internal nullptr dereferences.

Usually, stack implementations throw an exception, unless the environment forbids those or safety is sacrificed to gain some minimal performance.

2. Why it’s better to use size_t for count?

This point has been up for debate quite a lot, and most often the consensus is: Don't use unsigned values for sizes, as it can cause unexpected interactions with signed values.

It got into the standard library as "the" size type because they wanted to use another bit for size (in order to use up to 4 GiB RAM on 32-bit machines), but in hindsight (and with modern 64-bit processors) the unexpected interactions with signed values tipped the scale towards that conclusion.

3. I didn’t use new to create the stack in main(). Do I need to call the destructor? If no, why? If yes, how should I do it?

sasa and sec in main have automatic storage duration, which means that they get automatically destructed once they fall out of scope (at the closing } of main) in reverse order of construction.

4. According to the rule of three, how will I define the assignment operator for stack? Can you give one example?

The "Rule of Three" got extended to "Rule of Five" in C++11 and onwards in order to accomodate for move constructors and move assignment operators. So, let's get started with those additions (as they are fairly easy to implement):

MyStack(MyStack&& other) noexcept : top_node{other.top_node}, count{other.count} {
other.top_node = nullptr;
other.count = 0;
}

MyStack& operator=(MyStack&& other) noexcept {
if(this != &other) {
// destroy current list
clear();

// move others list
top_node = other.top_node;
count = other.count;

// leave other in a valid state
other.top_node = nullptr;
other.count = 0;
}

return *this;
}


One way to do the copy assignment operator is to use the copy-and-swap idiom:

MyStack& operator=(const MyStack& other) {
auto copy = other;
swap(other);
return *this;
}


But this requires a swap function, which might look like this:

void swap(MyStack& other) noexcept {
using std::swap;
swap(top_node, other.top_node);
swap(count, other.count);
}


Most implementations also provide a freestanding swap(MyType& a, MyType& b) function (which basically forwards to a.swap(b)) to allow their types to be used in this fashion.

5. I feel I have some misunderstanding about private. I put top_node in the private section, but why I am able to access top_node in the copy constructor?

You can access st.top_node and st.count inside the copy constructor because you are still inside the same class!

private just means "nobody outside of this class (or its friends) can see this" - but the copy constructor is obviously inside. (Otherwise, how could it initialize this->top_node?)

This level of access can also be granted to other classes or functions by making them a friend of the class:

class A;
void foo(B b);

class B {
friend class A;
friend void foo(B b);

int c;
};


Now B::c is visible inside A or foo, too.

Use this sparingly, though, as it breaks encapsulation. Sometimes it is needed, but more often than not there is a better alternative available.

• I think you should elaborate a bit on swap and operator= or maybe link to other resources like this. – yuri Aug 6 '18 at 7:34

I didn’t use new to create the stack in main(). Do I need to call the destructor? If no, why? If yes, how should I do it?

You do not need. It will be automatically called.

What should top() return if the stack is empty?

To be honest, it is your implementation you can do what you want. You can throw exception if you want.

I feel I have some misunderstanding about private. I put top_node in the private section, but why I am able to access top_node in the copy constructor?

It seems natural for me that you can, it is a class member function. You can read more here. Why can I access private variables in the copy constructor?

According to the rule of three, how will I define the assignment operator for stack? Can you give one example?

I would start using smart pointers in first place. It will really simplify all you need. Anyway there is also rule of five.

# Using new

In modern C++ code you should never see new. Read about smart pointers and use them. This will solve many problems.

# C.48: Prefer in-class initializers to member initializers in constructors for constant initializers

This

MyStack(): top_node(nullptr), count(0){};


Could be simply

Node* top_node {nullptr};
size_t count {0};


and

MyStack() = default;


Many of your questions seems more suitable for Stackoverflow, but I'll give a short answer here:

What should top() return if the stack is empty?

I would throw an exception.

I didn’t use new to create the stack in main(). Do I need to call the destructor? If no, why? If yes, how should I do it?

No, the destructor will be called automatically when the instance goes out of scope.

Other things:

• I would advise against using namespace std. Read here why

• I would remove the printouts in pop and top. If you really want to keep them, at least use cerr instead of cout.